Free lesson · DSA Mastery - Interview Prep, End to End

Course Schedule II

Hard11 min readdsagraphs

Course Schedule II

Course Schedule II is the first direct application of topological sort: given a number of courses and a list of prerequisite pairs, return a valid order in which to take all the courses, or an empty array if it's impossible (a prerequisite cycle exists). It is Kahn's algorithm applied almost verbatim - build the prerequisite graph, peel courses with no remaining prerequisites, and the peel order is the answer; if not all courses can be peeled, a cycle makes completion impossible. It cements the in-degree-peeling technique and the "incomplete order means cycle" insight on the textbook dependency-ordering problem. We present Kahn's algorithm (canonical) and DFS finish-time ordering (alternative).

The insight: courses are vertices; a prerequisite [a, b] ("to take a you must first take b") is a directed edge b → a (b comes before a). A valid schedule is a topological order of this graph. Kahn's algorithm produces it directly: start with courses that have no prerequisites (in-degree 0), take them, and each time a course is taken, "satisfy" it for its dependents by decrementing their in-degree; when a dependent's in-degree hits 0, all its prerequisites are met, so it becomes takeable. If you can take all courses this way, the peel order is a valid schedule; if a cycle blocks some, return empty.

The Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]   (or [0,2,1,3])

Explanation: Course 0 has no prerequisites. Courses 1 and 2 need 0. Course 3 needs 1 and 2.
A valid order takes 0 first, then 1 and 2 (either order), then 3.

Example 2:

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []

Explanation: 0 requires 1 and 1 requires 0 - a cycle. Impossible to finish; return empty.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2; all pairs distinct.

Approaches Overview

Both compute a topological order of the prerequisite graph. Kahn's peels courses with in-degree 0, appending each to the schedule and decrementing dependents' in-degrees; if all courses are peeled, the order is valid, else a cycle exists (return empty). DFS pushes courses on finish and reverses, using gray-node cycle detection. Both are O(V + E). Kahn's is the natural default - it directly models "take courses whose prerequisites are all done."

Approach 1: Kahn's Algorithm - Canonical

The Idea

Build the graph: for each prerequisite [a, b], add edge b → a and increment a's in-degree. Queue all courses with in-degree 0 (no prerequisites). Repeatedly take a course (append to the order), and for each course depending on it, decrement that dependent's in-degree; if it reaches 0, enqueue it. If the final order has all numCourses courses, return it; otherwise a cycle prevented completion - return an empty array.

Logic Flowchart

graph TD
    A["build graph: edge b→a per [a,b]; compute in-degrees"] --> B["queue all courses with in-degree 0"]
    B --> C{"queue non-empty?"}
    C -->|No| D{"order has all courses?"}
    C -->|Yes| E["take course u; append to order"]
    E --> F["for each dependent v: in-degree[v]--; if 0, enqueue"]
    F --> C
    D -->|Yes| G["return order (valid schedule)"]
    D -->|No| H["return [] (cycle: can't finish)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows Course Schedule II by Kahn's algorithm. Courses with no prerequisites are queued, taken in turn, and their dependents' prerequisite counts drop; if all courses are taken the order is valid, otherwise a cycle makes it impossible.

Code

public static 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]);                       // edge b → a (take b before a)
        indegree[p[0]]++;
    }

    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++)
        if (indegree[i] == 0) queue.offer(i);          // no prerequisites → takeable now

    int[] order = new int[numCourses];
    int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;                              // take this course
        for (int v : adj.get(u))
            if (--indegree[v] == 0) queue.offer(v);    // v's prerequisites now all satisfied
    }
    return idx == numCourses ? order : new int[0];     // incomplete → cycle → empty
}

// Usage:
// findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) -> [0,1,2,3] (or [0,2,1,3])
// findOrder(2, [[1,0],[0,1]]) -> []

This Java code finds a course order with Kahn's algorithm: it queues courses with no prerequisites, takes each in turn appending to the order, and decrements dependents' counts, returning the order if all courses are taken or empty if a cycle remains.

Step-by-Step Walkthrough

A frame-by-frame trace on Example 1, numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]:

graph LR
    F0["edges: 0→1, 0→2, 1→3, 2→3. in-degrees: 0:0, 1:1, 2:1, 3:2"]
    F1["queue=[0]. take 0 → order=[0]. dependents 1,2: in-deg → 0 each → enqueue"]
    F2["take 1 → order=[0,1]. dependent 3: in-deg 2→1. take 2 → order=[0,1,2]. 3: 1→0 → enqueue"]
    F3["take 3 → order=[0,1,2,3]. all 4 taken → return [0,1,2,3]"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough schedules courses: course zero has no prerequisites and is taken first, unlocking one and two, which then unlock three, giving the order zero one two three.

Result: [0,1,2,3].

Complexity

Time: O(V + E) - each course and prerequisite processed once. Space: O(V + E) for the graph, in-degrees, queue.

Approach 2: DFS Finish-Time Ordering - Alternative

The Idea

Build the same b → a graph. DFS each unvisited course; on finishing a course (after all courses depending on it are explored), push it onto a stack. Use gray-node tracking to detect cycles (a back edge to a course on the current recursion path means a cycle → return empty). The schedule is the stack popped in reverse finish order.

Code

public static int[] findOrderDFS(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]);   // b → a

    int[] state = new int[numCourses];                 // 0=unvisited,1=gray,2=done
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++)
        if (state[i] == 0 && !dfs(i, adj, state, stack))
            return new int[0];                         // cycle

    int[] order = new int[numCourses];
    for (int i = 0; i < numCourses; i++) order[i] = stack.pop();   // reverse finish order
    return order;
}

private static boolean dfs(int u, List<List<Integer>> adj, int[] state, Deque<Integer> stack) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) return false;               // back edge → cycle
        if (state[v] == 0 && !dfs(v, adj, state, stack)) return false;
    }
    state[u] = 2;
    stack.push(u);                                     // finished → push (post-order)
    return true;
}

// Usage: findOrderDFS(4, [[1,0],[2,0],[3,1],[3,2]]) -> a valid order like [0,2,1,3]

This Java code finds a course order with DFS: it explores each course's dependents first, pushes the course on finish, detects cycles via gray-node tracking, and reads the stack in reverse for the schedule.

Complexity

Time: O(V + E). Space: O(V + E) for the graph, state, stack, recursion.

Complexity Comparison

Both produce a valid course schedule (a topological order) in O(V + E). Kahn's peels courses with no remaining prerequisites, naturally modeling "take what you can now," with cycle detection falling out (incomplete order ⇒ cycle). DFS pushes courses on finish and reverses. Kahn's is the default for scheduling problems because the in-degree peeling maps so directly onto the real-world process.

Variations & Follow-ups

Why does the prerequisite pair [a, b] become the edge b → a?

The pair [a, b] means "to take course a, you must first take course b" - b is a prerequisite of a. In a topological order, prerequisites come before the courses that need them, so b must appear before a. A directed edge in topological sort points from the earlier vertex to the later one (u → v means u before v), so the edge is b → a (b before a). This direction is the single most common source of bugs in course-scheduling problems: it's easy to reflexively write a → b from the pair [a, b], which reverses every dependency and produces a wrong (or reverse) order. Always reason from the meaning: "b before a" ⇒ edge b → a. Equivalently, a's in-degree counts its prerequisites (the things that must come before it), so the edge must point into a from each prerequisite b - again b → a. Getting this direction right is the foundational step; everything downstream (in-degrees, peeling order) depends on it. When in doubt, sanity-check with a tiny example: course 1 needs course 0 ([1,0]) should make 0 come first, which the edge 0 → 1 achieves.

Why does "couldn't take all courses" mean there's a cycle, and why is that the impossibility condition?

Kahn's algorithm takes a course only when its in-degree reaches 0 - when all its prerequisites have been taken. If the algorithm finishes (queue empties) but fewer than numCourses courses were taken, the leftover courses never reached in-degree 0, meaning each of them always had at least one un-taken prerequisite. The only way a set of courses can all perpetually wait on each other is a cycle: course x waits on y, y waits on z, ..., looping back to x, so none can ever be the "first" to be taken. A cycle in the prerequisite graph means a circular dependency - you'd need to take x before y and y before x, impossible. This is exactly why a topological order exists only for DAGs: a cycle makes completion impossible. So "incomplete peel ⇒ cycle ⇒ return empty" is both the cycle-detection mechanism and the impossibility condition. The elegance of Kahn's algorithm is that cycle detection isn't a separate step - it's a free byproduct of counting how many courses got taken (idx == numCourses). Example 2's mutual prerequisite ([1,0] and [0,1]) is the minimal cycle: neither course ever has in-degree 0, so neither is takeable, and the order stays empty.

Why is the topological order not unique, and how would you get a specific one (e.g., lexicographically smallest)?

When two courses have no dependency relationship between them (neither is a prerequisite of the other, directly or transitively), they can be taken in either relative order - both are valid. In Example 1, courses 1 and 2 both depend only on 0 and neither depends on the other, so [0,1,2,3] and [0,2,1,3] are both correct. Kahn's algorithm's output depends on the queue's order: whichever of the in-degree-0 courses is dequeued first goes earlier. With a plain FIFO queue, the order reflects insertion order. The problem here accepts any valid order, so this freedom is fine. But some problems demand a specific order - most commonly the lexicographically smallest valid order. To get that, replace the FIFO queue with a min-heap (priority queue): always take the smallest-numbered course among those currently available (in-degree 0). This greedily picks the smallest legal next course at each step, yielding the lexicographically smallest topological order, at the cost of an O(log V) factor per operation (O((V + E) log V) total). The flexibility of Kahn's algorithm - swap the queue's discipline to control which valid order you get - is a useful lever: FIFO for any order, min-heap for lexicographically smallest, and other priority rules for other tie-breaking requirements.

How does Course Schedule II relate to Course Schedule (I), and what's the broader pattern?

Course Schedule (I) asks only whether you can finish all courses - a yes/no question, equivalent to "is the prerequisite graph acyclic?" Course Schedule II asks for the actual order. They're the same algorithm: Course Schedule I is Course Schedule II that returns a boolean (idx == numCourses) instead of the order array. This mirrors the two questions topological sort answers (from the introduction): "does an ordering exist?" (I) and "what is one?" (II), both resolved by Kahn's algorithm - the peel either completes (acyclic, order found) or stalls (cycle, impossible). The broader pattern is dependency resolution: model items as vertices and "must come before" as directed edges, then topologically sort. This applies far beyond courses - build systems (compile dependencies before dependents), task schedulers, spreadsheet cell recalculation (evaluate cells before those referencing them), package managers (install dependencies first), and more. The recurring recognition cue is prerequisite/dependency language ("before," "requires," "depends on"). Once you spot it and get the edge direction right, Kahn's algorithm (or DFS ordering) produces the schedule and detects impossibility. Course Schedule II is the textbook instance that anchors this pattern for the rest of the sub-group.

What about edge cases?

• No prerequisites: Every course has in-degree 0; any order of all courses works (e.g., [0, 1, ..., n-1]).
• Cycle (Example 2): No course reaches in-degree 0 to break the loop; incomplete order → empty array.
• Single course: Trivially [0].
• Linear chain (0 → 1 → 2 → ...): Exactly one valid order, the chain itself.
• Disconnected courses: Independent components are interleaved freely; any valid interleaving works.

Common Interview Pitfalls

• Reversing the edge direction. [a, b] means b before a, so edge b → a; getting this backward reverses the schedule.
• Forgetting the cycle check. Return empty if fewer than numCourses courses are peeled.
• Returning a partial order on a cycle. A cycle means no valid order; return empty, not the courses you managed to take.
• Using a stack/DFS but forgetting to reverse. DFS pushes on finish; the order is the reverse of finish times.

Why This Topic Matters

Course Schedule II is the textbook topological-ordering problem: model prerequisites as directed edges ([a,b] ⇒ b → a), then Kahn's algorithm peels courses with no remaining prerequisites - the peel order is a valid schedule, and an incomplete peel signals a cycle (impossible, return empty). It cements in-degree peeling, the correct edge direction, the "incomplete order ⇒ cycle" insight, and the min-heap variant for lexicographically smallest order - the foundation for every dependency-resolution problem in this sub-group.

The next topic, Find Eventual Safe States, applies topological-sort thinking to a subtler question: in a directed graph, a node is "safe" if every path starting from it eventually reaches a terminal node (one with no outgoing edges) - equivalently, no path from it can get stuck in a cycle. Find all safe nodes. The technique reframes it as a topological sort on the reversed graph (peeling terminal nodes and those leading only to safe nodes), or as DFS cycle detection where any node on or leading into a cycle is unsafe. It extends topological reasoning from "ordering" to "classifying nodes by their relationship to cycles," deepening the connection between topological sort and cycle structure.

Back to DSA Mastery - Interview Prep, End to End