Course Schedule II (LC 210)

Pattern: Topological Sort (Kahn’s BFS) — Return a Valid Order Difficulty: Medium Key Concept: Same as LC 207, but instead of just true/false, return one valid topological ordering. If a cycle exists, return an empty array.

Problem Statement

numCourses courses, prerequisites[i] = [a, b] means you must take b before a. Return any valid order of courses to take all of them, or [] if impossible.

Example

• numCourses = 2, prerequisites = [[1,0]] → [0, 1]
• numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] → [0,1,2,3] or [0,2,1,3]
• numCourses = 2, prerequisites = [[1,0],[0,1]] → []

---

1. Algorithm & Pseudocode

build adjacency list and in-degree array
queue = all nodes with in-degree 0
result = empty list
while queue not empty:
    u = queue.poll(); result.add(u)
    for v in adj[u]:
        if --in[v] == 0: queue.offer(v)
return result.size() == numCourses ? result : []

---

2. Step-by-Step Analysis

Why Kahn’s gives a valid order Nodes with no remaining prerequisites are “ready”. We process one, remove its outgoing edges (decrement neighbors’ in-degree), and any neighbor whose in-degree hits 0 becomes “ready”. This is a valid order because at each step, we choose a node whose prerequisites are all satisfied.

Why result.size() < n implies a cycle Cycle nodes always have at least one incoming edge from another cycle node — their in-degree never reaches 0, so they’re never enqueued.

Choice of queue order Kahn’s allows multiple valid topological orders. The order depends on how the queue tie-breaks equal-priority ready nodes. Use a min-heap for lexicographically smallest order if needed.

ASCII Trace for numCourses=4, prereqs=[[1,0],[2,0],[3,1],[3,2]]

edges: 0→1, 0→2, 1→3, 2→3
in-deg: [0,1,1,2]
queue start: [0]
poll 0 → result=[0]; dec 1→0, 2→0; queue=[1,2]
poll 1 → result=[0,1]; dec 3→1
poll 2 → result=[0,1,2]; dec 3→0; queue=[3]
poll 3 → result=[0,1,2,3]
size == n → return [0,1,2,3]

---

3. Java Solution

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);

        int[] result = new int[numCourses];
        int idx = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            result[idx++] = u;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
        }

        return idx == numCourses ? result : new int[0];
    }
}

Time: (O(V + E)) Space: (O(V + E))

---

4. The “Java vs. Others” Edge

• We write directly into int[] result and track idx — avoids List→array conversion.
• For “smallest lexicographic order”, swap ArrayDeque for PriorityQueue<Integer> — note: O((V+E) log V) instead of O(V+E).
• The DFS variant (post-order, then reverse) also works but is harder to get right when also detecting cycles.

---

5. Complexity Summary

Approach	Time	Space	Notes
Kahn’s	O(V + E)	O(V + E)	Cleanest; detects cycle by leftover count
DFS	O(V + E)	O(V + E)	Need 3-color cycle detection