Topics › Graphs › Topo Sort and Problems

Course Schedule II

Medium TUF ID 505 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

There are numCourses courses labelled 0 to numCourses - 1, and a list prerequisites where {a, b} means course b must be finished before course a. Return an ordering of all courses that respects every prerequisite. If several orderings work, return any of them. If no ordering exists, return an empty array.

Constraints: 1 ≤ numCourses ≤ 2000, 0 ≤ prerequisites.length ≤ numCourses × (numCourses - 1), pairs are valid course numbers.

Example 1

numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
answer = [0, 1, 2, 3]     // [0, 2, 1, 3] is equally correct: 1 and 2 only need 0

Example 2

numCourses = 2, prerequisites = [[0, 1], [1, 0]]
answer = []               // 0 and 1 wait for each other

Modelling. Each course is a node and each pair {a, b} is an edge b → a. The answer is a topological order of this graph: a list in which every edge points from an earlier entry to a later one. It exists exactly when the graph has no directed cycle. Course Schedule I asked only whether the order exists; here we must produce it, and every approach below is a way of building it.

static List<List<Integer>> buildGraph(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]);
    return adj;
}

Because many orders can be valid, the Java tests do not compare against one fixed answer. They check that the result is a permutation of all courses in which each prerequisite appears before its course, and compare exact arrays only for inputs that have a single valid order, such as a chain.

Approach 1: Brute force, simulate semesters

Intuition. Each semester, take every course whose prerequisites are all done, and write those courses down. Courses taken in the same semester do not depend on each other, so the order within a semester does not matter. The written list is a valid schedule. If a semester arrives in which courses remain but none can be taken, we are stuck forever: every remaining course waits on another remaining course, and following those waits must loop, which is a cycle.

Algorithm.

1. Keep taken, the answer array order and a counter count.
2. Each round, mark as blocked every course with an untaken prerequisite.
3. Append every course that is neither taken nor blocked to order.
4. If nothing was appended this round, return an empty array. Stop when count == numCourses.

static int[] bruteForce(int numCourses, int[][] prerequisites) {
    boolean[] taken = new boolean[numCourses];
    int[] order = new int[numCourses];
    int count = 0;
    while (count < numCourses) {
        boolean[] blocked = new boolean[numCourses];
        for (int[] p : prerequisites) {
            if (!taken[p[1]]) blocked[p[0]] = true;
        }
        int before = count;
        for (int c = 0; c < numCourses; c++) {
            if (!taken[c] && !blocked[c]) {
                taken[c] = true;
                order[count++] = c;
            }
        }
        if (count == before) return new int[0];           // stuck: the rest are on or behind a cycle
    }
    return order;
}

Complexity. Time O(V × (V + E)): up to V rounds (a chain frees one course per round), each scanning all pairs and all courses. Space O(V) for the arrays.

Approach 2: DFS, reverse post-order

Intuition. Run DFS along the edges b → a, from a course to the courses it unlocks. When the call for u finishes, every course reachable from u, meaning everything that directly or indirectly needs u, has already finished too. So if we write each course into the answer at the moment it finishes, filling the array from the back, then u lands to the left of everything that depends on it. That is precisely a topological order.

Why does every edge u → v end up pointing left to right? When DFS examines that edge from u, v is in one of three states:

• new: DFS descends into v, which finishes before u does, so v is written further right.
• done: v already finished and was written further right.
• on the current path: then v ⇝ u → v is a cycle and no order exists.

So the same DFS both builds the order and detects impossibility.

Algorithm.

1. Keep state (0 new, 1 on path, 2 done) and a write position slot starting at the last index.
2. For each new course, call place.
3. In place(u): set state 1; for each neighbour v, fail if it is on the path, recurse if it is new.
4. Set state 2, write u at slot, and move slot one step left.

static int[] dfsPostorder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = buildGraph(numCourses, prerequisites);
    int[] state = new int[numCourses];                    // 0 = new, 1 = on current path, 2 = done
    int[] order = new int[numCourses];
    int[] slot = {numCourses - 1};                        // next free position, filled right to left
    for (int c = 0; c < numCourses; c++) {
        if (state[c] == 0 && !place(c, adj, state, order, slot)) return new int[0];
    }
    return order;
}

/** Returns false if a cycle is found below u. */
static boolean place(int u, List<List<Integer>> adj, int[] state, int[] order, int[] slot) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) return false;
        if (state[v] == 0 && !place(v, adj, state, order, slot)) return false;
    }
    state[u] = 2;
    order[slot[0]--] = u;
    return true;
}

slot is a one-element array so that the recursive calls can share and update a single counter; a static field or a small class would work as well.

Complexity. Time O(V + E): each course is placed once and each edge examined once. Space O(V + E) for the graph, plus the state array and up to V levels of recursion.

Approach 3: Optimal, Kahn’s algorithm

Intuition. Kahn’s algorithm is the semester simulation without the rescanning. Keep, for each course, the number of prerequisites it is still waiting for (its in-degree). A course becomes available only when one of its prerequisites is finished, so when we finish a course we decrement only its dependents, and any that reach zero join the queue. The order in which courses leave the queue is a valid schedule, because a course enters the queue only after all of its prerequisites have left it.

If a cycle exists, the courses on it never reach in-degree zero, the queue empties early, and fewer than numCourses courses were written. We then return an empty array, never the partial list.

Algorithm.

1. Build the graph and in-degrees.
2. Queue all courses with in-degree 0.
3. Pop a course, append it to order, decrement each dependent, and queue any that reach 0.
4. Return order if all courses were appended, otherwise an empty array.

static int[] optimal(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = buildGraph(numCourses, prerequisites);
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) indegree[p[0]]++;
    Deque<Integer> queue = new ArrayDeque<>();
    for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) queue.add(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.add(v);
        }
    }
    return idx == numCourses ? order : new int[0];
}

Dry run on Example 1 (edges 0→1, 0→2, 1→3, 2→3):

Four courses written out of four, so [0, 1, 2, 3] is returned.

Complexity. Time O(V + E): each course is queued once and each edge decremented once. Space O(V + E) for the adjacency list, in-degrees, queue and answer.

Kahn’s algorithm is the usual interview choice: it is iterative, its correctness argument is short, and it produces the order in the natural left-to-right direction. The DFS version is equally fast and is worth knowing because the same reverse post-order idea appears in other graph algorithms, such as Kosaraju’s.

Edge cases and pitfalls

• Returning a partial order. When a cycle exists, Kahn’s loop still writes the courses that were freed before it got stuck. Always check the count and return an empty array.
• Edge direction. {a, b} means b first, so the edge is b → a. If you build a → b by mistake the cycle test still works, but the returned order is reversed and wrong.
• Self-prerequisite. {0, 0} is a one-node cycle; every approach returns an empty array.
• Duplicate pairs. The in-degree counts both copies and both copies are decremented, so nothing special is needed. The test [[2, 0], [2, 0], [1, 2]] has the single answer [0, 2, 1].
• Courses with no prerequisites at all. They have in-degree 0 from the start and may appear anywhere that respects the other constraints; with no pairs at all, any permutation is valid.
• Several valid answers. Do not test with a fixed array unless the order is forced.

Related problems

• Course Schedule I asks only whether such an order exists.
• Topo Sort covers the DFS-based order used in Approach 2.
• Topological sort or Kahn’s algorithm covers the queue-based order used in Approach 3.
• Alien Dictionary produces a topological order of letters.
• Shortest path in DAG uses a topological order to relax edges in one pass.