Builds on Level-Order BFS, which you haven’t finished yet.
Topological Sort (Kahn's Algorithm)
queue.You have numCourses courses to complete, numbered 0 through numCourses - 1, and a list prerequisites where each entry [ai, bi] means course bi must be completed before course ai.
- So an entry
[0, 1]means course1has to be finished before course0.
Produce one valid order in which all courses can be taken; any correct order is acceptable. If no order can complete every course, return an empty list instead.
Topological Sort
in-degree 0 vertices ➔ drain dependencies ➔ linear topological order- You must check where every path from one start ends, as in All Paths from Source Lead to Destination (LC 1059), not put all the nodes in an order. See Cycle Detection
| 1 | from collections import deque, defaultdict |
| 2 | from typing import List |
| 3 | |
| 4 | def topological_sort(num_courses: int, prerequisites: List[List[int]]) -> List[int]: |
| 5 | """Course Schedule II with Kahn's algorithm: an order to take every course, or [] if impossible. |
| 6 | Time: O(V + E) | Space: O(V + E) |
| 7 | """ |
| 8 | adj = defaultdict(list) |
| 9 | in_degree = [0] * num_courses |
| 10 | |
| 11 | for dest, src in prerequisites: # [a, b] means b before a: edge b -> a |
| 12 | adj[src].append(dest) |
| 13 | in_degree[dest] += 1 |
| 14 | |
| 15 | queue = deque([i for i in range(num_courses) if in_degree[i] == 0]) # No prerequisites left |
| 16 | order = [] |
| 17 | |
| 18 | while queue: |
| 19 | node = queue.popleft() |
| 20 | order.append(node) |
| 21 | for neighbor in adj[node]: |
| 22 | in_degree[neighbor] -= 1 # One prerequisite of neighbor is done |
| 23 | if in_degree[neighbor] == 0: |
| 24 | queue.append(neighbor) |
| 25 | |
| 26 | return order if len(order) == num_courses else [] # Nodes left over: a cycle |
order or in queue comes after all of its prerequisites, and in_degree[v] counts the prerequisites of v not yet in order.A course can be taken once all its prerequisites are done, so count each node's in_degree, start queue with every node whose count is 0, and each time you pop node, lower its neighbours' counts and add any that reach 0. A node enters queue only after every edge into it has been removed, so it lands in order after all its prerequisites. The trap is the cycle check: nodes on a cycle never reach 0, so return order only when len(order) == num_courses, never a partial order.
See it run
Topological Sort (Kahn's algorithm), step by step
queue [0]order []in_degree [0, 1, 1, 2]
Each column is a course number. The rows are in_degree, queue (front on the left) and order.
nodethe course just popped from queue and added to orderneighbora course that depends on node; its count drops by 1pusheda course with count 0, added to queue
Each pair [a, b] adds an edge b -> a and raises in_degree[a]. The counts are [0, 1, 1, 2].
Gotcha 1 of 3
- The trap
Gotcha 1: Returning
orderwithout checkinglen(order) == num_coursesMistakereturn orderFixreturn order if len(order) == num_courses else []What happens: A course on a cycle waits for another course on the same cycle. Its
in_degreenever reaches 0, so it never entersqueue.orderthen holds only the courses outside the cycle. Returning that partial order says the schedule is possible when it is not.Example: Course Schedule II (LC 210): numCourses = 3, prerequisites = [[1,0],[2,1],[1,2]]Mistake: returns [0]Fix: returns []
Deep Dive
What the in-degree counts, and why it works
A prerequisite pair [a, b] means that course b must come before course a. The card turns it into an edge b -> a. The in_degree of a course is the number of edges that point into it, which is the number of prerequisites it still waits for.
A course with in_degree 0 waits for nothing, so it can be taken now. Taking it finishes one prerequisite for each course that depends on it. So in_degree[neighbor] -= 1 records that one prerequisite is done.
A course enters queue only when its count reaches 0. At that moment every prerequisite of it has already been taken. This is the invariant: every node in order or in queue comes after all of its prerequisites.
A trace on four courses
Take Course Schedule II (LC 210) with num_courses = 4 and prerequisites = [[1,0],[2,0],[3,1],[3,2]]. The edges are 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3. The counts are in_degree = [0, 1, 1, 2].
Only course 0 has count 0, so queue = [0]. Pop 0 and put it in order. The edge 0 -> 1 lowers in_degree[1] to 0, so 1 joins queue. The edge 0 -> 2 does the same for 2.
Pop 1. The edge 1 -> 3 lowers in_degree[3] from 2 to 1. Course 3 still waits for course 2, so it does not join queue. Pop 2. The edge 2 -> 3 lowers in_degree[3] to 0, so 3 joins queue. Pop 3, which has no edges.
The result is order = [0, 1, 2, 3]. Its length is 4, which equals num_courses, so the answer is valid.
The cycle check
If courses depend on each other in a loop, no course in the loop can go first. Each of them waits for another course of the loop, so its count never reaches 0 and it never enters queue.
Example: num_courses = 3 and prerequisites = [[1,0],[2,1],[1,2]]. Course 0 has count 0 and is taken. After that, course 1 waits for course 2, and course 2 waits for course 1. Both counts stay at 1. order is [0], which is shorter than 3.
So the card ends with return order if len(order) == num_courses else []. Without it, the function would return [0] and claim that a schedule exists. The same check answers Course Schedule (LC 207), which only asks whether all courses can finish.
The cost and what the order means
Building adj and in_degree reads each prerequisite pair once. The loop pops each course at most once and follows each edge once. The time is O(V + E), where V is num_courses and E is the number of pairs. The space is O(V + E) for adj, in_degree, queue and order.
Many correct orders can exist. In the trace, [0, 2, 1, 3] is also valid. LeetCode accepts any valid order, and the card returns the one that follows the queue.
The same loop solves Alien Dictionary (LC 269). Letters are the nodes, and each pair of neighbouring words gives one edge between the first letters that differ.
60-Second Pitch
"I treat each prerequisite pair as a directed edge and count the incoming edges of every course in in_degree. A course with count 0 has no unfinished prerequisite, so I put it in a queue. When I pop a course, I add it to order and lower the count of each course that depends on it. A course whose count reaches 0 joins the queue. If order has all num_courses courses, it is a valid schedule. If it is shorter, the remaining courses are on a cycle and I return an empty list. Each course and each edge is handled once, so the time is O(V + E)."
Common Questions
- How does the algorithm detect a cycle?
Every course on a cycle waits for another course of the same cycle, so its
in_degreenever reaches 0. It never entersqueueand never entersorder. After the loop,len(order)is smaller thannum_courses, and the function returns[].- What are the time and space complexity?
O(V + E)time andO(V + E)space. The code reads each pair once to buildadjandin_degree. The loop pops each course once and follows each edge once. The space holdsadj,in_degree,queueandorder.- Is the order unique?
No. Whenever
queueholds more than one course, any of them can go first. In the four-course example,[0, 1, 2, 3]and[0, 2, 1, 3]are both valid. The problems that need one exact order add a rule for ties, for example the smallest letter first, and use a heap instead of a plain queue.- How is this different from a depth-first search for topological order?
Both give a valid order in
O(V + E). The depth-first version uses three states per node and puts a node in the answer after all its descendants, then reverses the list. Kahn's algorithm needs no recursion, so it has no stack-depth problem, and its cycle check is the single testlen(order) == num_courses.- How do you handle the course-schedule input format?
A pair
[a, b]meansbbeforea, so the edge isb -> aandin_degree[a]goes up. The loopfor dest, src in prerequisitesnames the two values by their role. Reading the pair in the other direction produces the order backwards.
SWE Reasoning
Spot it
- Tasks, courses or build steps have prerequisites, and the question asks for an order that respects all of them.
- The question asks whether all tasks can finish. The answer is no when the prerequisites contain a cycle.
- The relations are directed:
bbeforeadoes not meanabeforeb. - Several tasks may be valid at once, and any valid order is accepted.
The invariant, step by step
- For each pair
[dest, src], adddesttoadj[src]and add 1 toin_degree[dest]. Nowin_degree[v]counts the prerequisites ofv. queuestarts with every course whose count is 0. These courses wait for nothing, so they are safe to take first.node = queue.popleft()takes a safe course and appends it toorder. Everything it needs is already inorder.- For each
neighborofnode,in_degree[neighbor] -= 1records that one prerequisite is done. - When a count reaches 0, all prerequisites of
neighborare inorder, soneighborjoinsqueue. - When
queueis empty, every course that could be placed has been placed. Iflen(order) == num_courses,orderis a valid order. If not, the missing courses wait on a cycle.
Traps
- No length check. Returning
orderafter a cycle gives a partial order. For[[1,0],[2,1],[1,2]]it returns[0]instead of[]. - Edge in the wrong direction. Using
adj[dest].append(src)makes every course come before its prerequisites. For[[1,0]]it returns[1, 0]instead of[0, 1]. - Seeding
queuewith course 0 only. Courses with count 0 can be in separate groups. A group that is never seeded never entersorder, and the length check wrongly returns[]. - Checking the count before lowering it. Test
in_degree[neighbor] == 0after the-= 1, not before. A course would otherwise enterqueueone step late or never.
Practice
Builds on Level-Order BFS, which you haven’t finished yet.
Topological Sort (Kahn's Algorithm)
queue.You have numCourses courses to complete, numbered 0 through numCourses - 1, and a list prerequisites where each entry [ai, bi] means course bi must be completed before course ai.
- So an entry
[0, 1]means course1has to be finished before course0.
Produce one valid order in which all courses can be taken; any correct order is acceptable. If no order can complete every course, return an empty list instead.
Topological Sort
in-degree 0 vertices ➔ drain dependencies ➔ linear topological order- You must check where every path from one start ends, as in All Paths from Source Lead to Destination (LC 1059), not put all the nodes in an order. See Cycle Detection
| 1 | from collections import deque, defaultdict |
| 2 | from typing import List |
| 3 | |
| 4 | def topological_sort(num_courses: int, prerequisites: List[List[int]]) -> List[int]: |
| 5 | """Course Schedule II with Kahn's algorithm: an order to take every course, or [] if impossible. |
| 6 | Time: O(V + E) | Space: O(V + E) |
| 7 | """ |
| 8 | adj = defaultdict(list) |
| 9 | in_degree = [0] * num_courses |
| 10 | |
| 11 | for dest, src in prerequisites: # [a, b] means b before a: edge b -> a |
| 12 | adj[src].append(dest) |
| 13 | in_degree[dest] += 1 |
| 14 | |
| 15 | queue = deque([i for i in range(num_courses) if in_degree[i] == 0]) # No prerequisites left |
| 16 | order = [] |
| 17 | |
| 18 | while queue: |
| 19 | node = queue.popleft() |
| 20 | order.append(node) |
| 21 | for neighbor in adj[node]: |
| 22 | in_degree[neighbor] -= 1 # One prerequisite of neighbor is done |
| 23 | if in_degree[neighbor] == 0: |
| 24 | queue.append(neighbor) |
| 25 | |
| 26 | return order if len(order) == num_courses else [] # Nodes left over: a cycle |
order or in queue comes after all of its prerequisites, and in_degree[v] counts the prerequisites of v not yet in order.A course can be taken once all its prerequisites are done, so count each node's in_degree, start queue with every node whose count is 0, and each time you pop node, lower its neighbours' counts and add any that reach 0. A node enters queue only after every edge into it has been removed, so it lands in order after all its prerequisites. The trap is the cycle check: nodes on a cycle never reach 0, so return order only when len(order) == num_courses, never a partial order.
See it run
Topological Sort (Kahn's algorithm), step by step
queue [0]order []in_degree [0, 1, 1, 2]
Each column is a course number. The rows are in_degree, queue (front on the left) and order.
nodethe course just popped from queue and added to orderneighbora course that depends on node; its count drops by 1pusheda course with count 0, added to queue
Each pair [a, b] adds an edge b -> a and raises in_degree[a]. The counts are [0, 1, 1, 2].
Gotcha 1 of 3
- The trap
Gotcha 1: Returning
orderwithout checkinglen(order) == num_coursesMistakereturn orderFixreturn order if len(order) == num_courses else []What happens: A course on a cycle waits for another course on the same cycle. Its
in_degreenever reaches 0, so it never entersqueue.orderthen holds only the courses outside the cycle. Returning that partial order says the schedule is possible when it is not.Example: Course Schedule II (LC 210): numCourses = 3, prerequisites = [[1,0],[2,1],[1,2]]Mistake: returns [0]Fix: returns []
Deep Dive
What the in-degree counts, and why it works
A prerequisite pair [a, b] means that course b must come before course a. The card turns it into an edge b -> a. The in_degree of a course is the number of edges that point into it, which is the number of prerequisites it still waits for.
A course with in_degree 0 waits for nothing, so it can be taken now. Taking it finishes one prerequisite for each course that depends on it. So in_degree[neighbor] -= 1 records that one prerequisite is done.
A course enters queue only when its count reaches 0. At that moment every prerequisite of it has already been taken. This is the invariant: every node in order or in queue comes after all of its prerequisites.
A trace on four courses
Take Course Schedule II (LC 210) with num_courses = 4 and prerequisites = [[1,0],[2,0],[3,1],[3,2]]. The edges are 0 -> 1, 0 -> 2, 1 -> 3 and 2 -> 3. The counts are in_degree = [0, 1, 1, 2].
Only course 0 has count 0, so queue = [0]. Pop 0 and put it in order. The edge 0 -> 1 lowers in_degree[1] to 0, so 1 joins queue. The edge 0 -> 2 does the same for 2.
Pop 1. The edge 1 -> 3 lowers in_degree[3] from 2 to 1. Course 3 still waits for course 2, so it does not join queue. Pop 2. The edge 2 -> 3 lowers in_degree[3] to 0, so 3 joins queue. Pop 3, which has no edges.
The result is order = [0, 1, 2, 3]. Its length is 4, which equals num_courses, so the answer is valid.
The cycle check
If courses depend on each other in a loop, no course in the loop can go first. Each of them waits for another course of the loop, so its count never reaches 0 and it never enters queue.
Example: num_courses = 3 and prerequisites = [[1,0],[2,1],[1,2]]. Course 0 has count 0 and is taken. After that, course 1 waits for course 2, and course 2 waits for course 1. Both counts stay at 1. order is [0], which is shorter than 3.
So the card ends with return order if len(order) == num_courses else []. Without it, the function would return [0] and claim that a schedule exists. The same check answers Course Schedule (LC 207), which only asks whether all courses can finish.
The cost and what the order means
Building adj and in_degree reads each prerequisite pair once. The loop pops each course at most once and follows each edge once. The time is O(V + E), where V is num_courses and E is the number of pairs. The space is O(V + E) for adj, in_degree, queue and order.
Many correct orders can exist. In the trace, [0, 2, 1, 3] is also valid. LeetCode accepts any valid order, and the card returns the one that follows the queue.
The same loop solves Alien Dictionary (LC 269). Letters are the nodes, and each pair of neighbouring words gives one edge between the first letters that differ.
60-Second Pitch
"I treat each prerequisite pair as a directed edge and count the incoming edges of every course in in_degree. A course with count 0 has no unfinished prerequisite, so I put it in a queue. When I pop a course, I add it to order and lower the count of each course that depends on it. A course whose count reaches 0 joins the queue. If order has all num_courses courses, it is a valid schedule. If it is shorter, the remaining courses are on a cycle and I return an empty list. Each course and each edge is handled once, so the time is O(V + E)."
Common Questions
- How does the algorithm detect a cycle?
Every course on a cycle waits for another course of the same cycle, so its
in_degreenever reaches 0. It never entersqueueand never entersorder. After the loop,len(order)is smaller thannum_courses, and the function returns[].- What are the time and space complexity?
O(V + E)time andO(V + E)space. The code reads each pair once to buildadjandin_degree. The loop pops each course once and follows each edge once. The space holdsadj,in_degree,queueandorder.- Is the order unique?
No. Whenever
queueholds more than one course, any of them can go first. In the four-course example,[0, 1, 2, 3]and[0, 2, 1, 3]are both valid. The problems that need one exact order add a rule for ties, for example the smallest letter first, and use a heap instead of a plain queue.- How is this different from a depth-first search for topological order?
Both give a valid order in
O(V + E). The depth-first version uses three states per node and puts a node in the answer after all its descendants, then reverses the list. Kahn's algorithm needs no recursion, so it has no stack-depth problem, and its cycle check is the single testlen(order) == num_courses.- How do you handle the course-schedule input format?
A pair
[a, b]meansbbeforea, so the edge isb -> aandin_degree[a]goes up. The loopfor dest, src in prerequisitesnames the two values by their role. Reading the pair in the other direction produces the order backwards.
SWE Reasoning
Spot it
- Tasks, courses or build steps have prerequisites, and the question asks for an order that respects all of them.
- The question asks whether all tasks can finish. The answer is no when the prerequisites contain a cycle.
- The relations are directed:
bbeforeadoes not meanabeforeb. - Several tasks may be valid at once, and any valid order is accepted.
The invariant, step by step
- For each pair
[dest, src], adddesttoadj[src]and add 1 toin_degree[dest]. Nowin_degree[v]counts the prerequisites ofv. queuestarts with every course whose count is 0. These courses wait for nothing, so they are safe to take first.node = queue.popleft()takes a safe course and appends it toorder. Everything it needs is already inorder.- For each
neighborofnode,in_degree[neighbor] -= 1records that one prerequisite is done. - When a count reaches 0, all prerequisites of
neighborare inorder, soneighborjoinsqueue. - When
queueis empty, every course that could be placed has been placed. Iflen(order) == num_courses,orderis a valid order. If not, the missing courses wait on a cycle.
Traps
- No length check. Returning
orderafter a cycle gives a partial order. For[[1,0],[2,1],[1,2]]it returns[0]instead of[]. - Edge in the wrong direction. Using
adj[dest].append(src)makes every course come before its prerequisites. For[[1,0]]it returns[1, 0]instead of[0, 1]. - Seeding
queuewith course 0 only. Courses with count 0 can be in separate groups. A group that is never seeded never entersorder, and the length check wrongly returns[]. - Checking the count before lowering it. Test
in_degree[neighbor] == 0after the-= 1, not before. A course would otherwise enterqueueone step late or never.