88.Course Schedule II

MediumGraphs · 9/19

Problem

There are numCourses courses labelled 0 to numCourses - 1. Each pair prerequisites[i] = [a, b] means course b must be taken before course a.

Return an ordering of courses that lets you finish all of them. If several orderings are valid, return any of them. If it is impossible (the prerequisites contain a cycle), return an empty array.

Examples

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: Course 1 requires course 0, so 0 must come first.

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: 0 first; 1 and 2 each need only 0; 3 needs both 1 and 2. [0,2,1,3] is also accepted.

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []
Explanation: The two courses depend on each other, so no order exists.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a, b < numCourses, a != b
All pairs [a, b] are distinct

💡 Key Insight

A valid course order is a topological order of the directed graph with edges b → a (prerequisite before course). It exists exactly when the graph is acyclic. Kahn's algorithm builds the order directly: repeatedly output a course with in-degree 0 and remove its outgoing edges. If fewer than numCourses courses are output, the leftovers form a cycle and the answer is []. Everything runs in O(V + E).

Brute Force (Repeated Elimination Rounds)

TimeO(V·(V + E))SpaceO(V)

Intuition

Plan semester by semester. In each round, scan every prerequisite pair to find which untaken courses are still blocked; every course that is not blocked can be taken now, so append it to the order. When a round adds nothing, stop. If the order contains every course, return it; otherwise there is a cycle.

Algorithm

taken[] all false, order empty.
Repeat:
- blocked[a] = true for each [a, b] with b not taken.
- Append every course that is neither taken nor blocked; mark it taken.
- If no course was appended this round, stop.
Return order if it has numCourses entries, else an empty array.

Visualization

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

round 1: blocked {1,2,3} → order = [0]
round 2: blocked {3}     → order = [0,1,2]
round 3: blocked {}      → order = [0,1,2,3]
round 4: nothing new     → stop, size 4 → return [0,1,2,3]

Code

java

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        boolean[] taken = new boolean[numCourses];
        int[] order = new int[numCourses];
        int size = 0;

        while (true) {
            boolean[] blocked = new boolean[numCourses];
            for (int[] p : prerequisites) {
                if (!taken[p[1]]) blocked[p[0]] = true; // prerequisite still missing
            }
            boolean progress = false;
            for (int course = 0; course < numCourses; course++) {
                if (!taken[course] && !blocked[course]) {
                    taken[course] = true;
                    order[size++] = course;
                    progress = true;
                }
            }
            if (!progress) break;
        }
        return size == numCourses ? order : new int[0];
    }
}

Complexity

Time: O(V·(V + E)) — up to V rounds, each scanning all pairs and all courses.
Space: O(V) — taken, blocked and order.

DFS Post-Order

TimeO(V + E)SpaceO(V + E)

Intuition

Point edges from each course to its prerequisites (a → b). In a DFS, a course is appended to the answer only after all of its prerequisites have been fully explored (post-order), so prerequisites always appear earlier in the list. A three-state colouring detects cycles: meeting a node that is still "visiting" means we looped back onto the current path.

Algorithm

Build graph[a].add(b) for every [a, b].
For each course in state 0, run dfs(course); if it reports a cycle, return [].
dfs(u): if state[u] == 1 → cycle; if state[u] == 2 → done. Otherwise set state[u] = 1, DFS every prerequisite, set state[u] = 2, and append u to order.
Return order.

Dry Run

graph (course -> prerequisites):  1→0, 2→0, 3→1, 3→2

dfs(0): no prerequisites           → order = [0]
dfs(1): prerequisite 0 is done     → order = [0,1]
dfs(2): prerequisite 0 is done     → order = [0,1,2]
dfs(3): prerequisites 1, 2 done    → order = [0,1,2,3]

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<Integer>> graph;
    private int[] state; // 0 = unvisited, 1 = visiting, 2 = done
    private int[] order;
    private int size;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            graph.get(p[0]).add(p[1]); // course -> its prerequisite
        }
        state = new int[numCourses];
        order = new int[numCourses];
        size = 0;

        for (int course = 0; course < numCourses; course++) {
            if (state[course] == 0 && !dfs(course)) return new int[0];
        }
        return order;
    }

    // Returns false if a cycle is found
    private boolean dfs(int u) {
        if (state[u] == 1) return false; // back edge: cycle
        if (state[u] == 2) return true;
        state[u] = 1;
        for (int pre : graph.get(u)) {
            if (!dfs(pre)) return false;
        }
        state[u] = 2;
        order[size++] = u; // all prerequisites are already in order
        return true;
    }
}

Complexity

Time: O(V + E) — each course is finished once and each edge is followed once.
Space: O(V + E) — adjacency lists, state, order and recursion depth up to V.

Kahn's Topological SortOptimal

TimeO(V + E)SpaceO(V + E)

Intuition

Count each course's unmet prerequisites (indegree). Courses with indegree == 0 are available now: put them in a queue. Each time we take a course, append it to the order and decrement the indegree of every course that depended on it; those that hit 0 join the queue. This is the round-based idea without any rescanning. If the order ends up shorter than numCourses, a cycle blocked the rest.

Algorithm

Build graph[b].add(a) and indegree[a]++ for every [a, b].
Enqueue all courses with indegree == 0.
While the queue is non-empty: pop u, append it to order; for each v in graph[u], decrement indegree[v] and enqueue v when it reaches 0.
Return order if its size is numCourses, else [].

Dry Run

flowchart TD
    S["indegree 0:0 1:1 2:1 3:2<br/>queue [0]"] --> A["pop 0 → order [0]<br/>1:0, 2:0 → queue [1, 2]"]
    A --> B["pop 1 → order [0,1]<br/>3:1"]
    B --> C["pop 2 → order [0,1,2]<br/>3:0 → queue [3]"]
    C --> D["pop 3 → order [0,1,2,3]"]
    D --> E{"size == 4?"}
    E -->|"yes"| F["return [0,1,2,3]"]
    E -->|"no"| G["return []"]

Code

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

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

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        int[] order = new int[numCourses];
        int size = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[size++] = u;
            for (int v : graph.get(u)) {
                if (--indegree[v] == 0) queue.offer(v); // v is now unlocked
            }
        }
        return size == numCourses ? order : new int[0]; // short order means a cycle
    }
}

Complexity

Time: O(V + E) — each course is enqueued once and each edge is relaxed once.
Space: O(V + E) — adjacency lists, indegree, the queue and order.

Complexity Comparison

Approach	Time	Space
Repeated Elimination Rounds	O(V·(V + E))	O(V)
DFS Post-Order	O(V + E)	O(V + E)
Kahn's Topological Sort	O(V + E)	O(V + E)

Common Pitfalls

Returning a partial order when a cycle exists — the problem requires an empty array.
Mixing edge directions in DFS: with course → prerequisite edges the post-order is already correct; with prerequisite → course edges you must reverse the post-order.
Returning null instead of new int[0].
Forgetting courses that appear in no pair at all; they still have to be in the output (in-degree 0).
Detecting cycles with a plain visited flag, which wrongly rejects shared prerequisites (diamond shapes).