Problem 210

Abstract / Summary

Find an order to take all courses given their prerequisites or determine if it is not possible.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0210.py

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Kahn's algorithm
        start = set(range(numCourses))
        need  = defaultdict(set)

        # courses without any prerequisites
        for p in prerequisites:
            start.discard(p[0])
            need[p[0]].add(p[1])

        result = []
        done   = set()
        # pick next course
        while start:
            next = start.pop()
            if next not in done:
                result += [ next ]
            done.add(next)

            candidates = []
            for n in need:
                need[n].discard(next)
                if n not in done and len(need[n]) == 0:
                    candidates.append(n)

            for c in candidates:
                start.add(c)
                del need[c]

        # still some courses not taken ?
        if len(result) < numCourses:
            return []
        else:
            return result
35 lines | 1020 bytes | submitted September 4, 2023 | GitHub   15% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 56% (3+ million submissions).

Typical patterns to solve this problem:
  • Breadth First Search
  • Depth First Search
  • Graph Theory
  • Topological Sort
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the course-schedule ordering problem using Kahn’s topological-sorting algorithm. It builds a representation of prerequisite relationships, repeatedly selects courses that have no remaining unmet prerequisites, and assembles a linear ordering that satisfies all constraints. If a complete ordering cannot be produced (for example, when a cycle exists), the function returns an empty list.

Initialization

start = set(range(numCourses))
need  = defaultdict(set)

start holds every course identifier initially, assuming all courses are ready to be taken. need maps a course to the set of courses it depends on. Using a set for start enables O(1) membership checks and fast removal of courses as they become unavailable. The defaultdict(set) automatically creates an empty prerequisite set for any new key, avoiding explicit existence checks later.

Building the prerequisite map

for p in prerequisites:
    start.discard(p[0])
    need[p[0]].add(p[1])

Each prerequisite pair [a, b] indicates that course a requires b. The loop removes a from start because it now has at least one prerequisite, ensuring that start only contains courses with zero incoming edges. Simultaneously, need[a] is populated with b. The use of discard prevents errors if a course appears multiple times; it silently does nothing when the element is absent.

Result containers

result = []
done   = set()

result accumulates the final ordering. done records courses that have already been placed, providing O(1) checks for duplicates and preventing re-processing of the same course.

Main processing loop

while start:
    next = start.pop()
    if next not in done:
        result += [ next ]
    done.add(next)

    candidates = []
    for n in need:
        need[n].discard(next)
        if n not in done and len(need[n]) == 0:
            candidates.append(n)

    for c in candidates:
        start.add(c)
        del need[c]

The loop continues while there are courses with no outstanding prerequisites.

  • start.pop() extracts an arbitrary ready course. Because start is a set, the extraction order is nondeterministic but still valid for topological sorting.

  • The conditional if next not in done: guards against accidental duplication; the subsequent done.add(next) guarantees that the course is marked as processed.

  • The inner for n in need: iterates over all courses that still have prerequisite sets. For each, need[n].discard(next) removes the just-completed course from its prerequisite list. If this removal empties the set and the course has not been processed, it becomes a candidate for the next round.

  • Candidates are collected in a temporary list to avoid modifying need while iterating over it. After the inner loop, each candidate is added back to start, and its entry is removed from need with del need[c]. Deleting the entry frees memory early and keeps the need dictionary size minimal as the algorithm progresses.

The design leverages set operations (discard, len == 0) that run in constant time on average, reducing overhead compared with list-based approaches.

Final validation

if len(result) < numCourses:
    return []
else:
    return result

After the loop, if the number of courses placed in result is less than the total number of courses, some courses remain unprocessed, indicating a cycle or unsatisfied prerequisite chain. In that case the function returns an empty list to signal impossibility. Otherwise, the complete ordering is returned.

Edge-case handling

  • No prerequisites - When prerequisites is empty, the initial loop never removes any course from start. Consequently, all courses remain in start and are sequentially popped, producing a list containing every course identifier.

  • Single course - With numCourses == 1, start begins as {0}. The loop processes the sole element, adds it to result, and exits. The final length check succeeds, returning [0].

  • Duplicate prerequisite entries - If the same prerequisite pair appears multiple times, need[p[0]].add(p[1]) stores the dependency only once because a set eliminates duplicates. The subsequent discard operations also remain safe, as discarding an element that is already absent has no effect.

  • Self-dependency - A pair like [i, i] adds i to its own prerequisite set. The algorithm will never be able to clear that set because i cannot be removed from need[i] before i itself is processed. Consequently, i never re-enters start, and the final length check fails, resulting in an empty list.

  • Disconnected subgraphs - Courses that belong to separate prerequisite clusters are all represented in start initially if they have no incoming edges. The algorithm processes each cluster independently, eventually merging their results into a single ordering.

  • Complete cycle - When every course participates in a cycle, the initial start set becomes empty because each course is removed during the prerequisite-building phase. The main loop never executes, result stays empty, and the final check returns an empty list.

Performance-related choices

  • Using a set for start provides constant-time removal and membership testing, which is crucial when repeatedly selecting the next available course.

  • Storing prerequisites in a defaultdict(set) enables O(1) addition and removal of individual dependencies, avoiding linear scans that would be required with list structures.

  • The discard method is employed instead of remove to prevent exceptions on redundant removals, eliminating the need for explicit existence checks.

  • Deleting entries from need as soon as a course becomes eligible (del need[c]) reduces the size of the dictionary, shrinking the iteration workload in subsequent passes.

  • Accumulating candidates in a temporary list before modifying start avoids concurrent modification of the dictionary while iterating, preserving iteration correctness without additional overhead.

  • The final length comparison (len(result) < numCourses) offers a single, inexpensive verification step to detect cycles, rather than maintaining separate cycle-detection structures.

Overall, the implementation combines set-based data structures with careful in-place updates to achieve an efficient topological sort that gracefully handles a variety of input configurations.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you are building a giant tower out of blocks, but some blocks need another block underneath them before you can put them on top. The number of courses is the total amount of blocks you have to stack. The parts labeled prerequisites are the rules about which blocks have to be placed before others.

The code starts by looking for all the blocks that do not have anything waiting underneath them. These are the easy ones you can start with right away. It keeps a list of these starting blocks.

Whenever a block is placed, the code checks if any other blocks were waiting for that specific one to be finished. If a block was waiting for that one and it has no other requirements left, that new block becomes ready to be placed next.

This process repeats by grabbing a ready block, placing it into a pile called the result, and checking if any new blocks can be placed because of it. If everything goes well and all the blocks find their spot in the pile, the work is finished. If there are still blocks left over that could not be placed because of a tricky rule, the pile is empty.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 6 | μ = 5.77 | σ = 1.40

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java C# Rust TS Go
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
FelixFan1122 C#
fengvyi C++
fpdjsns C++
fsq Python
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
luangong TS
MacJim C++
martianoff Scala
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
XiaotaoGuo C++
yuanliu666 Kotlin
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
FelixFan1122 C#
fengvyi C++
fpdjsns C++
fsq Python
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
luangong TypeScript
MacJim C++
martianoff Scala
ruoru Rust
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
XiaotaoGuo C++
yuanliu666 Kotlin
zfang399 C++
55 links | 39 authors | 11 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Course Schedule II - Topological Sort - Leetcode 210'
NeetCode 18 mins
Course Schedule II - Topological Sort - Leetcode 210
YouTube video 'Course Schedule II | LeetCode 210 | C++, Java, Python'
Knowledge Center 22 mins
Course Schedule II | LeetCode 210 | C++, Java, Python
YouTube video '[Java] Topological Sort Algorithm | Solve Course Schedule I & II'
Eric Programming 34 mins
[Java] Topological Sort Algorithm | Solve Course Schedule I & II
YouTube video 'LeetCode 207 & 210: Course Schedule I & II | Topological Sort | Kahn's algorithm - Interview Ep 78.2'
Fisher Coder 10 mins
LeetCode 207 & 210: Course Schedule I & II | Topological Sort | Kahn's algorithm - Interview Ep 78.2
YouTube video 'Course Schedule II 🔥 | Leetcode 210 | Graph'
Ayushi Sharma 17 mins
Course Schedule II 🔥 | Leetcode 210 | Graph
YouTube video 'COURSE SCHEDULE II | LEETCODE # 210 | PYTHON TOPOLOGICAL SORT SOLUTION'
Cracking FAANG 21 mins
COURSE SCHEDULE II | LEETCODE # 210 | PYTHON TOPOLOGICAL SORT SOLUTION
YouTube video 'Course Schedule II | Leetcode 210 | Live coding session 🔥🔥🔥 | Topological Sort nailed !!!!'
Coding Decoded 14 mins
Course Schedule II | Leetcode 210 | Live coding session 🔥🔥🔥 | Topological Sort nailed !!!!
YouTube video 'Python Implementation LeetCode 210. Course Schedule II Explanation and Solution'
happygirlzt 11 mins
Python Implementation LeetCode 210. Course Schedule II Explanation and Solution
YouTube video 'Course Schedule II | Day 18 Topological Sort | [ July LeetCoding Challenge ] [ Leetcode #210] [2020]'
Algorithms Made Easy 6 mins
Course Schedule II | Day 18 Topological Sort | [ July LeetCoding Challenge ] [ Leetcode #210] [2020]
YouTube video 'Course Schedule II (LeetCode) | DFS Topological Sort Explanation'
Jyotinder Singh 17 mins
Course Schedule II (LeetCode) | DFS Topological Sort Explanation
YouTube video 'Python Implementation LeetCode 210. Course Schedule II 中文解释'
happygirlzt 11 mins
Python Implementation LeetCode 210. Course Schedule II 中文解释
YouTube video 'LeetCode 210 | Course Schedule II | HashMap BFS | Java'
Sleepy Cracker 7 mins
LeetCode 210 | Course Schedule II | HashMap BFS | Java
YouTube video 'Daily Leetcode #632: Dec 23, 2021 - 210. Course Schedule II'
Programming Live with Larry 11 mins
Daily Leetcode #632: Dec 23, 2021 - 210. Course Schedule II
YouTube video 'Daily Leetcode #109: Jul 18, 2020 - 210. Course Schedule II'
Programming Live with Larry 14 mins
Daily Leetcode #109: Jul 18, 2020 - 210. Course Schedule II
YouTube video 'Google Coding Interview Question | Leetcode 210 | Course Schedule II'
WorkWithGoogler 18 mins
Google Coding Interview Question | Leetcode 210 | Course Schedule II
YouTube video 'LeetCode 210. Course Schedule II - (Kahn's Algorithm / BFS)'
Kacy Codes 11 mins
LeetCode 210. Course Schedule II - (Kahn's Algorithm / BFS)
YouTube video '87. Leetcode 210. Course Schedule II : Javascript'
Web Fusion with Bharadwaj 27 mins
87. Leetcode 210. Course Schedule II : Javascript
YouTube video 'LeetCode 210. Course Schedule II - (DFS)'
Kacy Codes 13 mins
LeetCode 210. Course Schedule II - (DFS)
YouTube video 'Leetcode 210: Course Schedule II in Telugu | Kahn’s Algorithm | Python DSA | srkcodes'
Srk Codes 9 mins
Leetcode 210: Course Schedule II in Telugu | Kahn’s Algorithm | Python DSA | srkcodes
YouTube video 'Course Schedule II - LeetCode #210 - C++'
Sean Chuah 9 mins
Course Schedule II - LeetCode #210 - C++
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

9 similar problems

Solved On The Same Day

25 solutions   September 4, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality