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 valid
In plain English, you must take numCourses courses. You are given an array of prerequisites where prerequisites[i] = [a, b] indicates you must take course b before course a. Return an array of the courses in a valid order to take them. If there are multiple valid orders, return any of them. If it's impossible to take all courses (because of a cycle), return an empty array.
Any valid order is accepted, which matters: a graph usually has many topological orders.
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.
Think of Kahn's algorithm like writing down a recipe. In Course Schedule I, you were just checking if the recipe could be completed without an impossible loop. In Course Schedule II, you actually write down the steps on a piece of paper as you do them. When you find a step that has no prerequisites (like "get bowl"), you write it down on your order list and mentally cross it off. You keep writing down steps as they become available. The final list you wrote down is your answer!
This is what a topological sort is: an ordering of a directed acyclic graph where every edge points forwards.
from collections import dequeclass Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: adj = [[] for _ in range(numCourses)] # (1) indegree = [0] * numCourses for course, prereq in prerequisites: # (2) adj[prereq].append(course) # prereq → course indegree[course] += 1 queue = deque(c for c in range(numCourses) if indegree[c] == 0) # (3) order = [] # (4) while queue: c = queue.popleft() # (5) order.append(c) # (6) ← the only real change for nxt in adj[c]: # (7) indegree[nxt] -= 1 if indegree[nxt] == 0: queue.append(nxt) return order if len(order) == numCourses else [] # (8)
ts
function findOrder(numCourses: number, prerequisites: number[][]): number[] { const adj: number[][] = Array.from({ length: numCourses }, () => []); // (1) const indegree = new Array(numCourses).fill(0); for (const [course, prereq] of prerequisites) { // (2) adj[prereq].push(course); indegree[course]++; } const queue: number[] = []; // (3) for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c); const order: number[] = []; // (4) let head = 0; while (head < queue.length) { const c = queue[head++]; // (5) order.push(c); // (6) for (const nxt of adj[c]) { // (7) if (--indegree[nxt] === 0) queue.push(nxt); } } return order.length === numCourses ? order : []; // (8)}
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.
This is 4.20.8 Course Schedule with one change: instead of only counting finished courses, we record them in the order they finish.
(1) Build the graph: for each course, the courses that depend on it, plus
(2) a count of unfinished prerequisites for each course.
(3) Start with every course that has no prerequisites.
(4) The order we will return.
(5) Take a course that is ready. All of its prerequisites have already been taken.
(6) Add it to the order. This is the only real change from Course Schedule. Because a course only becomes ready after all its prerequisites are in the order, every course appears after the courses it needs.
(7) Each dependent course now has one fewer prerequisite. Any that reach zero join the queue.
(8) If every course made it into the order, return it. Otherwise a loop of prerequisites blocked some courses, and no valid order exists, so return an empty list.
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] # reverse
Why 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.
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.
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.
"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.