Graphs · LC #210
Course Schedule II
Return a valid course order (topological sort) by collecting nodes in DFS postorder and reversing, or return empty array if a cycle is detected.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
There are `numCourses` courses labeled 0 to `numCourses - 1`. Given `prerequisites[i] = [ai, bi]` indicating course `bi` must be taken before `ai`, return the ordering of courses you should take to finish all courses. If it is impossible to finish all courses (cycle exists), return an empty array.
Sample I/O
Input: numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] (or [0,1,2,3]) Input: numCourses=2, prerequisites=[[0,1],[1,0]] Output: []
Time: O(V+E) · Space: O(V+E)
Intuition
How to Think About It
Intuition
Topological sort: nodes must appear before all their dependents. DFS naturally produces reverse topological order - a node is appended to the result AFTER all nodes it depends on (its DFS subtree) are processed. Reversing the postorder list gives a valid topological ordering.
Core Concept
DFS postorder collection. Same 3-state coloring as Course Schedule I. Append node to order list when state transitions to 2 (done). Reverse the list at the end. If cycle detected (state 1 encountered), return []. Alternative: Kahn's BFS - maintain in-degree counts, process zero-in-degree nodes, detect cycle if all nodes not processed.
When to use
Any problem requiring a valid ordering of tasks with dependencies (build systems, package managers, compilation order, task scheduling). When you need the ordering itself, not just cycle detection.
When NOT to use
When only cycle detection is needed (Course Schedule I is simpler). When the graph is undirected. When multiple valid orderings exist and you need a specific one (need deterministic tiebreaking).
Key Insights
What to Know Cold
- Postorder = process node after ALL descendants are processed. This guarantees prerequisites appear earlier in the reversed list.
- The reversal step is critical: postorder collects dependents before prerequisites, so reversing gives correct order.
- Kahn's BFS alternative enqueues nodes with in-degree 0; as edges are removed, newly zero-in-degree nodes are enqueued. More intuitive for some.
- Both DFS and Kahn's produce valid (though potentially different) topological orderings.
- If cycle detected, the partial order array is invalid - return empty immediately.
1 example
Worked Examples
DFS postorder topological sort
4 courses, prerequisites [[1,0],[2,0],[3,1],[3,2]] - course 0 must be taken first.
3-state DFS; append to order on state→2; reverse and return.
function findOrder(n: number, prereqs: number[][]): number[] {
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of prereqs) graph[b].push(a);
const state = new Array(n).fill(0);
const order: number[] = [];
const dfs = (v: number): boolean => {
if (state[v] === 1) return false; // cycle
if (state[v] === 2) return true;
state[v] = 1;
for (const nb of graph[v]) if (!dfs(nb)) return false;
state[v] = 2;
order.push(v);
return true;
};
for (let i = 0; i < n; i++) if (state[i] === 0 && !dfs(i)) return [];
return order.reverse();
}Output: [0, 2, 1, 3]
Topological sort is a fundamental graph algorithm. Interviewers expect you to know both DFS-postorder and Kahn's BFS variants and to explain why postorder reversal works.