Appearance
4.20.9 — Course Schedule II
LeetCode 210 · Medium
The problem
Return an order in which all courses can be taken, or an empty array if it is impossible.
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
→ [0,1,2,3] or [0,2,1,3] — both validAny valid order is accepted, which matters: a graph usually has many topological orders.
The pattern
4.20.8 already computed this. Kahn's algorithm takes courses one at a time in an order that respects every prerequisite — that sequence is the answer. The previous problem simply threw it away and kept the count.
So the change is two lines: collect the courses as you take them, and return the list instead of a boolean.
This is what a topological sort is: an ordering of a directed acyclic graph where every edge points forwards.
The solution
python
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, prereq in prerequisites:
adj[prereq].append(course) # prereq → course
indegree[course] += 1
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c) # ← the only real change
for nxt in adj[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []ts
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
const adj: number[][] = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
adj[prereq].push(course);
indegree[course]++;
}
const queue: number[] = [];
for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c);
const order: number[] = [];
let head = 0;
while (head < queue.length) {
const c = queue[head++];
order.push(c);
for (const nxt of adj[c]) {
if (--indegree[nxt] === 0) queue.push(nxt);
}
}
return order.length === numCourses ? order : [];
}return order if complete else []. A short order means a cycle, and the problem wants an empty array in that case — not the partial order. Returning the partial list is a real bug, because it looks like a valid schedule.
A course enters the queue exactly once, at the moment its last prerequisite is removed. So order holds each course once and its length is the natural completeness check.
The DFS version, and why the order comes out reversed
DFS also produces a topological order, with one twist worth understanding.
Do a depth-first walk. When a node has finished — that is, all of its dependents are done — push it onto a list. Then reverse the list at the end.
python
def findOrder(self, numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
adj[prereq].append(course)
state = [0] * numCourses # 0 unvisited, 1 in progress, 2 done
order = []
def dfs(c) -> bool:
if state[c] == 1: return False # cycle
if state[c] == 2: return True
state[c] = 1
for nxt in adj[c]:
if not dfs(nxt): return False
state[c] = 2
order.append(c) # finished: everything after it is placed
return True
for c in range(numCourses):
if not dfs(c): return []
return order[::-1] # reverseWhy reverse? A node is appended only after every node that depends on it has been appended. So the list is built from the last course backwards, and reversing puts the prerequisites first.
That is the post-order position doing the work, exactly as in the tree chapter: the node acts only after its children are finished.
Complexity
O(V + E) time and space for both versions.
The follow-up: how many semesters
If you may take any number of courses at once, provided their prerequisites are done, the minimum number of semesters is the number of levels in Kahn's algorithm.
Everything sitting in the queue at the same moment has no unmet prerequisites and none depends on another, so they can all be taken together. Process the queue level by level, freezing its length as in 4.14.8, and count the rounds.
That number is the longest chain of prerequisites in the graph — the critical path. Real project schedulers compute exactly this, and it is where the term "critical path" comes from.
Where this goes next
- Alien Dictionary — build the graph from sorted words, then topologically sort it. The hard part is deriving the edges, not the sort. 4.21.
- Parallel Courses, Minimum Time to Complete All Tasks — the level-counting follow-up above.
- Sequence Reconstruction — is the topological order unique? It is, exactly when the queue never holds more than one node at a time. Neat, and easy to check.
- Real systems —
make, Bazel, npm's dependency resolution, spreadsheet recalculation, and database migration ordering all run this.
What the interviewer will push on
"Is the order unique?" No, in general. It is unique exactly when Kahn's queue never holds more than one node.
"What do you return on a cycle?" An empty array. Not the partial order.
"BFS or DFS?" Kahn's is iterative, gives the cycle check for free, and extends to the semester question. DFS needs a reversal and can hit stack limits.
"Why does the DFS order need reversing?" Nodes are appended after everything depending on them, so the list is built backwards.
"How many semesters minimum?" The number of levels, which is the longest prerequisite chain.
One thing to volunteer: point out that this is Course Schedule with two lines changed, and that Kahn's was already computing the order. Recognising that a previous problem's discarded work is this problem's answer is exactly the kind of connection worth showing.
Next: 4.20.10 Redundant Connection — the first union-find problem, where edges arrive one at a time.