Course Schedule II

Problem

LeetCode 210 — Course Schedule II

Given n courses labeled 0 to n-1 and a list of prerequisite pairs [a, b] meaning “must take b before a”, return a valid ordering to finish all courses. Return an empty array if it’s impossible (cycle exists).

Example

n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
output = [0, 1, 2, 3]  (or [0, 2, 1, 3])

Approach — Kahn’s BFS (Topological Sort)

1. Build an adjacency list and an inDegree[] array from the prerequisites.
2. Seed a queue with every node whose inDegree == 0 (no prerequisites).
3. Repeatedly pop a course, add it to the result, and decrement the in-degree of all its dependents. Any dependent that reaches inDegree == 0 joins the queue.
4. If the result contains all n courses → valid order. Otherwise a cycle exists → return [].

Why it detects cycles: nodes inside a cycle never reach inDegree == 0, so they never enter the queue and the final count falls short of n.

Complexity

• Time: O(n + E) — each node and edge is processed exactly once
• Space: O(n + E) — adjacency list + in-degree array + queue

Solution

class Solution {
    public int[] findOrder(int n, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[n];

        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++)
            if (inDegree[i] == 0) queue.offer(i);

        int[] result = new int[n];
        int idx = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[idx++] = course;
            for (int next : adj.get(course))
                if (--inDegree[next] == 0) queue.offer(next);
        }

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

Why It Teaches You Something

Kahn’s algorithm is the cleanest way to simultaneously produce a topological order and detect a cycle in one pass — no recursion, no visited/coloring state.

The same skeleton solves: