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
Difficulty
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
AI Disclaimer
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.
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. Becausestartis 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 subsequentdone.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
needwhile iterating over it. After the inner loop, each candidate is added back tostart, and its entry is removed fromneedwithdel need[c]. Deleting the entry frees memory early and keeps theneeddictionary 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
prerequisitesis empty, the initial loop never removes any course fromstart. Consequently, all courses remain instartand are sequentially popped, producing a list containing every course identifier. -
Single course - With
numCourses == 1,startbegins as{0}. The loop processes the sole element, adds it toresult, 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 subsequentdiscardoperations also remain safe, as discarding an element that is already absent has no effect. -
Self-dependency - A pair like
[i, i]addsito its own prerequisite set. The algorithm will never be able to clear that set becauseicannot be removed fromneed[i]beforeiitself is processed. Consequently,inever re-entersstart, and the final length check fails, resulting in an empty list. -
Disconnected subgraphs - Courses that belong to separate prerequisite clusters are all represented in
startinitially 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
startset becomes empty because each course is removed during the prerequisite-building phase. The main loop never executes,resultstays empty, and the final check returns an empty list.
Performance-related choices
-
Using a
setforstartprovides 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
discardmethod is employed instead ofremoveto prevent exceptions on redundant removals, eliminating the need for explicit existence checks. -
Deleting entries from
needas 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
startavoids 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.
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.
Code Quality
Complexity Analysis
Other Solutions
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++ |
Videos
Similar Problems
- problem 207: Course Schedule
- problem 269: Alien Dictionary
- problem 310: Minimum Height Trees
- problem 444: Sequence Reconstruction
- problem 630: Course Schedule III
- problem 1136: Parallel Courses
- problem 2115: Find All Possible Recipes from Given Supplies
- problem 2392: Build a Matrix With Conditions
- problem 2459: Sort Array by Moving Items to Empty Space
Solved On The Same Day
- problem 292: Nim Game
- problem 572: Subtree of Another Tree
- problem 617: Merge Two Binary Trees
- problem 671: Second Minimum Node In a Binary Tree
- problem 152: Maximum Product Subarray
- problem 207: Course Schedule
- problem 211: Design Add and Search Words Data Structure
- problem 213: House Robber II
- problem 237: Delete Node in a Linked List
- problem 260: Single Number III
- problem 416: Partition Equal Subset Sum
- problem 437: Path Sum III
- problem 450: Delete Node in a BST
- problem 560: Subarray Sum Equals K
- problem 606: Construct String from Binary Tree
- problem 623: Add One Row to Tree
- problem 652: Find Duplicate Subtrees
- problem 654: Maximum Binary Tree
- problem 655: Print Binary Tree
- problem 662: Maximum Width of Binary Tree
- problem 669: Trim a Binary Search Tree
- problem 687: Longest Univalue Path
- problem 1115: Print FooBar Alternately
- problem 1116: Print Zero Even Odd
Extra
- 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