Course Schedule II

MediumGraphs · Topological Sort🧩 Topological Sort LeetCode #210 ↗Updated Oct 30, 2026

Problem

There are numCourses courses labelled 0..n-1. A pair [a, b] means course b must be finished before course a. Return any order that completes every course, or an empty array if the prerequisites contain a cycle.

Inputn=2, [[1,0]]Output[0,1]

Inputn=4, [[1,0],[2,0],[3,1],[3,2]]Output[0,1,2,3] or [0,2,1,3]

Inputn=2, [[1,0],[0,1]]Output[]

1 ≤ V = numCourses ≤ 2000 · 0 ≤ E = |prerequisites| ≤ V(V-1) · all pairs distinct

Try it yourself

Java

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Draw an edge b → a for each pair: a valid schedule is a topological order of this directed graph, which exists iff the graph has no cycle. Repeatedly taking a course with in-degree 0 builds it in O(V + E).

PatternTopological Sort

Instinct Tasks with prerequisites, "X must come before Y", or an order hidden in comparisons: build a directed graph and peel off nodes with zero in-degree.

Memory hack No prereqs? Off you go. Each finished task frees its followers; if someone is never freed, there is a cycle.

Open the Topological Sort guide →

Approaches

Brute ForceRepeated Scan for Ready Courses

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

Keep sweeping over all courses; take any untaken course whose prerequisites are all taken. Stop when a full sweep makes no progress. If some course is still untaken, the remaining courses wait on each other — a cycle.

Java

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> pre = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) pre.add(new ArrayList<>());
    for (int[] p : prerequisites) pre.get(p[0]).add(p[1]);
    boolean[] taken = new boolean[numCourses];
    int[] order = new int[numCourses];
    int idx = 0;
    boolean progress = true;
    while (progress) {
        progress = false;
        for (int c = 0; c < numCourses; c++) {
            if (taken[c]) continue;
            boolean ready = true;
            for (int p : pre.get(c)) if (!taken[p]) { ready = false; break; }
            if (ready) { taken[c] = true; order[idx++] = c; progress = true; }
        }
    }
    return idx == numCourses ? order : new int[0];
}

Mirrors how a student would plan, but may need V sweeps over the whole graph.

BetterDFS Post-Order (3-Colour Cycle Check)

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

DFS along b → a edges. A course finishes only after every course depending on it has finished, so filling order from the back by finish time yields a valid schedule. Meeting a node still on the stack (state 1) means a back edge ⇒ cycle.

Java

private int idx;
public int[] findOrder(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[] state = new int[numCourses]; // 0 = new, 1 = on stack, 2 = done
    int[] order = new int[numCourses];
    idx = numCourses; // fill from the back
    for (int c = 0; c < numCourses; c++)
        if (state[c] == 0 && hasCycle(c, adj, state, order)) return new int[0];
    return order;
}
private boolean hasCycle(int u, List<List<Integer>> adj, int[] state, int[] order) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) return true;
        if (state[v] == 0 && hasCycle(v, adj, state, order)) return true;
    }
    state[u] = 2;
    order[--idx] = u;
    return false;
}

Linear, but recursion depth can reach V (stack-overflow risk on long chains).

OptimalKahn's Algorithm (BFS on In-Degrees)

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

Count prerequisites (indegree) per course and queue all courses with none. Taking a course decrements its dependents; any that hit 0 become available. If fewer than V courses are taken, the rest lie on a cycle.

Java

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[] indegree = new int[numCourses];
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) queue.offer(c);
    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;
        for (int v : adj.get(u)) if (--indegree[v] == 0) queue.offer(v);
    }
    return idx == numCourses ? order : new int[0];
}

Linear, iterative, and cycle detection is a single count check.

Pro tip

Swap the queue for a PriorityQueue to get the lexicographically smallest order (O((V + E) log V)).

At a glance

Level	Approach	Time	Space
Brute Force	Repeated Scan for Ready Courses	`O(V·(V + E))`	`O(V + E)`
Better	DFS Post-Order (3-Colour Cycle Check)	`O(V + E)`	`O(V + E)`
Optimal	Kahn's Algorithm (BFS on In-Degrees)	`O(V + E)`	`O(V + E)`

Common pitfalls

Reversing the edge — [a, b] means b → a.
Using a 2-state visited array in DFS — can't tell a cycle from a revisit.
Returning a partial order instead of [] when a cycle exists.

Interview tips

Name it: “topological sort; impossible iff there is a cycle”.
Prefer Kahn's in interviews — no recursion, simple cycle check.
Point out that many valid answers exist; any one is accepted.

Pattern

Topological sort → ordering tasks with “X before Y” dependencies, or detecting cycles in a directed graph.

My notes saved in this browser