Topological Sort — Course Schedule II
↗ LeetCode: Course Schedule II · Medium · pattern chapter →
Given numCourses and prerequisites[i] = [a, b] meaning "to take a you must first take b", return an ordering, or [] if impossible (cycle).
Example 1 — n=2, [[1,0]] → [0,1]Example 2 — n=4, [[1,0],[2,0],[3,1],[3,2]] → [0,1,2,3] or [0,2,1,3]Example 3 — n=2, [[1,0],[0,1]] → [] (cycle)
Constraints — 1 ≤ n ≤ 2000; 0 ≤ #prereqs ≤ n·(n−1)/2. Brute repeatedly scans for zero-indegree nodes: O(V·(V+E)) = 2000·(2000+5000) = 1.4·10⁷ ops. Kahn's queue-based BFS is O(V+E) = 7·10³ ops with built-in cycle detection.
Interview timer00:00
Approach 1 — Brute force (try every permutation)
Intuition. Enumerate every permutation; return the first that respects all prerequisites.
Complexity — Time O(n!) — impossible past n≈10.
Approach 2 — DFS with color marking (post-order)
Insight from brute. A course can be placed after all its prerequisites; DFS in post-order emits nodes in reverse topological order.
Use 3 colors: WHITE = unvisited, GRAY = on the current path (cycle detection), BLACK = finished.
Trap. If DFS revisits a GRAY node → cycle → return [].
int[] findOrderDFS(int n, int[][] prereqs) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prereqs) adj.get(p[1]).add(p[0]);
int[] color = new int[n];
LinkedList<Integer> post = new LinkedList<>();
for (int i = 0; i < n; i++) if (color[i] == 0 && !dfs(i, adj, color, post)) return new int[0];
int[] out = new int[n];
int k = 0;
for (int x : post) out[k++] = x;
return out;
}
boolean dfs(int u, List<List<Integer>> adj, int[] color, LinkedList<Integer> post) {
color[u] = 1; // gray
for (int v : adj.get(u)) {
if (color[v] == 1) return false; // back-edge → cycle
if (color[v] == 0 && !dfs(v, adj, color, post)) return false;
}
color[u] = 2; // black
post.addFirst(u); // prepend for reverse post-order
return true;
}Complexity — Time O(V + E); Space O(V + E). Optimal.
Approach 3 — Kahn's algorithm (BFS on in-degrees)
Insight from DFS. Iteratively remove nodes whose in-degree is 0 — they are "always safe next." Repeat until empty (or cycle).
Bonus. Kahn's naturally returns the topological order forward-emitting (no reverse); easier for interviewers to trust.
int[] findOrder(int n, int[][] prereqs) {
int[] indeg = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prereqs) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
int[] out = new int[n];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
out[k++] = u;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return k == n ? out : new int[0]; // cycle → k < n
}Complexity — Time O(V + E); Space O(V + E).
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Permutations | O(n!) | O(n) |
| DFS post-order | O(V + E) | O(V + E) |
| Kahn BFS | O(V + E) | O(V + E) |
When to use which
- Cold interview → Kahn is easier to explain and debug live.
- DFS variant → useful when you also need SCC or bridges.
- Cycle detection is the primary need → either works; DFS with color is cleaner.
Related problems (same ladder applies)
- Course Schedule I — Kahn returns just "can we finish?"
- Alien Dictionary — build the DAG from adjacent word pairs, then topo-sort
- Minimum Height Trees — peel leaves iteratively (topo-sort variant)
- Parallel Courses — Kahn tracking levels (semesters)