Course Schedule (LC 207)

Pattern: Topological Sort — Kahn’s BFS (in-degree based) Difficulty: Medium Key Concept: A directed graph has a valid order iff it has no cycle. Kahn’s algorithm processes nodes whose in-degree is 0; if all nodes get processed, the graph is acyclic.

Problem Statement

There are numCourses courses labeled 0..numCourses-1. Prerequisites are given as an array prerequisites where [a, b] means “to take course a you must first complete b” (an edge b → a).

Return true if you can finish all courses, else false.

Example

• numCourses = 2, prerequisites = [[1,0]] → true (take 0, then 1)
• numCourses = 2, prerequisites = [[1,0],[0,1]] → false (mutual dependency)

---

1. Algorithm & Pseudocode

Kahn’s BFS (Topological Sort)

build adjacency list adj[u] = list of v where (u → v) is an edge
build in-degree[] : in[v]++ for each edge u→v

queue = all nodes with in[v] == 0
processed = 0
while queue not empty:
    u = queue.poll()
    processed++
    for each neighbor v of u:
        if --in[v] == 0: queue.offer(v)

return processed == numCourses

DFS with color states

white = unvisited, gray = in stack, black = done
for each node not visited:
    if dfs(node) finds a back edge to gray → cycle
return no cycle found

---

2. Step-by-Step Analysis

Why Kahn’s works Nodes with no prerequisites can be taken first. Take them out → some other nodes lose their last prerequisite → they’re free → repeat. If at any point no node is free (queue empties early), the remaining nodes form a cycle.

Why edge direction matters The pair [a, b] means b is a prerequisite of a, so the directed edge is b → a. After taking b, course a’s in-degree drops by 1.

Why processed == numCourses is the cycle check Cycle nodes can never reach in-degree 0 (they always have at least one incoming edge from the cycle), so they’re never enqueued. If processed < numCourses, those leftover nodes are inside cycles.

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

edges:  0→1, 1→2, 2→3
in-degree: [0, 1, 1, 1]

queue start: [0]
poll 0 → processed=1; decrement in[1] → 0 → enqueue 1
poll 1 → processed=2; decrement in[2] → 0 → enqueue 2
poll 2 → processed=3; decrement in[3] → 0 → enqueue 3
poll 3 → processed=4
return processed == 4 → true

---

3. Java Solution

Kahn’s BFS

class Solution {
    public boolean canFinish(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 processed = 0;
        while (!q.isEmpty()) {
            int u = q.poll(); processed++;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
        }
        return processed == numCourses;
    }
}

DFS — Color States

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

        int[] color = new int[numCourses]; // 0=white, 1=gray, 2=black
        for (int i = 0; i < numCourses; i++)
            if (color[i] == 0 && hasCycle(i, adj, color)) return false;
        return true;
    }
    private boolean hasCycle(int u, List<List<Integer>> adj, int[] color) {
        color[u] = 1;
        for (int v : adj.get(u)) {
            if (color[v] == 1) return true;            // back edge → cycle
            if (color[v] == 0 && hasCycle(v, adj, color)) return true;
        }
        color[u] = 2;
        return false;
    }
}

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

---

4. The “Java vs. Others” Edge

• Building List<List<Integer>> is verbose — but unavoidable in Java; the for-loop allocation is idiomatic.
• For weighted variants, change adjacency to List<int[]>.
• For “return one valid order” (LC 210), append u to the result list inside Kahn’s loop. If result.size() < n at the end → empty array.

---

5. Complexity Summary

Approach	Time	Space	Notes
Kahn’s	O(V + E)	O(V + E)	Cleanest, also gives a valid order
DFS	O(V + E)	O(V + E)	Recursive; risks deep stack