Course Schedule II — Returning a Valid Topological Order

Problem Statement#

LeetCode 210 — Course Schedule II (Medium)

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, b] indicates that you must take course b first if you want to take course a.

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.

Constraints:

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

Example 1:

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

Example 2:

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

Example 3:

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

Why This Problem Matters#

Course Schedule II is the canonical topological-sort question at FAANG. The previous problem (LC 207) asks for a yes/no answer; this one demands the actual ordering, which forces you to use a constructive algorithm rather than a clever cycle-detection trick. Amazon, Google, and Meta all rotate this problem because it elegantly tests:

1. Kahn algorithm execution. Building in-degrees, seeding the queue with all zero-in-degree nodes, processing the BFS frontier.
2. Edge-direction discipline. [a, b] again means b before a, so edges go b -> a. Reversing this still ranks as the most common bug.
3. Cycle handling without leaking partial output. When a cycle blocks topological order, return [] rather than the partial sequence.

The pattern generalizes far beyond schoolwork. Build systems, package managers, ETL pipelines, migration scripts, and dataflow compilers all depend on stable topological orderings. Showing the interviewer you understand this is half the battle.

The Core Insight#

A topological order of a DAG is any linear arrangement of vertices such that for every directed edge u -> v, u precedes v. Two algorithms construct such an order in O(V + E):

• Kahn (BFS with in-degrees). Start from all nodes with in-degree zero; remove them and decrement in-degree of successors. The order they leave the queue is a valid topological order.
• DFS with post-order reversal. Run DFS; push each node onto a stack when its DFS finishes (post-order). The reversed stack is a valid topological order.

Kahn naturally detects cycles: if you process fewer than numCourses nodes, a cycle exists. The DFS approach must use three colors (white / gray / black) to detect cycles. For interview clarity, Kahn is usually the better choice.

A subtle insight: there is not a unique answer. Any valid order suffices. Mentioning this avoids confusion when your output differs from the expected sample.

Visual Dry Run#

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Edges (b -> a):

0 -> 1
0 -> 2
1 -> 3
2 -> 3
 
In-degrees: [0:0, 1:1, 2:1, 3:2]
 
queue = [0]                   order = []
Pop 0 -> push 0 to order.     order = [0]
  Decrement 1: 1 -> 0, push.
  Decrement 2: 1 -> 0, push.
 
queue = [1, 2]                order = [0]
Pop 1 -> order = [0, 1]
  Decrement 3: 2 -> 1.
 
queue = [2]                   order = [0, 1]
Pop 2 -> order = [0, 1, 2]
  Decrement 3: 1 -> 0, push.
 
queue = [3]                   order = [0, 1, 2]
Pop 3 -> order = [0, 1, 2, 3]
 
Length matches numCourses -> return order.

If we had added 3 -> 0, every in-degree would start positive, the queue would be empty, and we would return [].

Solution (Optimal)#

Python (Kahn — BFS Topological Sort)#

from collections import deque, defaultdict
 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        adj = defaultdict(list)                 # b -> list of courses requiring b
        in_degree = [0] * numCourses
 
        # Edge convention: b must come before a, so edge b -> a
        for a, b in prerequisites:
            adj[b].append(a)
            in_degree[a] += 1
 
        # Seed the BFS frontier with every node that has zero prerequisites
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        order = []
 
        while queue:
            course = queue.popleft()
            order.append(course)                # record this position in the order
            for nxt in adj[course]:
                in_degree[nxt] -= 1             # one prerequisite satisfied
                if in_degree[nxt] == 0:
                    queue.append(nxt)           # all prereqs done; ready to take
 
        # If a cycle prevented full processing, return empty
        return order if len(order) == numCourses else []

JavaScript (DFS Post-order)#

/**
 * Three-color DFS, push to order on finish.
 * Final order is the reverse of finish-time order.
 */
var findOrder = function(numCourses, prerequisites) {
    const adj = Array.from({length: numCourses}, () => []);
    for (const [a, b] of prerequisites) adj[b].push(a);   // b -> a
 
    const color = new Array(numCourses).fill(0);          // 0=white,1=gray,2=black
    const order = [];
 
    const dfs = (u) => {
        if (color[u] === 1) return false;                 // back edge -> cycle
        if (color[u] === 2) return true;                  // already finished
        color[u] = 1;                                     // mark in-path
        for (const v of adj[u]) {
            if (!dfs(v)) return false;                    // bubble up cycle
        }
        color[u] = 2;                                     // finished -> black
        order.push(u);                                    // post-order push
        return true;
    };
 
    for (let i = 0; i < numCourses; i++) {
        if (color[i] === 0 && !dfs(i)) return [];         // cycle detected
    }
    return order.reverse();                               // reverse post-order
};

Complexity. Both algorithms run in O(V + E) time and O(V + E) space. They are optimal for any topological sort because every edge must be inspected at least once.

Common Mistakes#

1. Reversing the edge direction. Make b -> a, not a -> b. This single bug accounts for the majority of failed submissions.
2. Returning the partial order on cycle. When len(order) smaller than numCourses, return []. Some candidates accidentally return whatever they have processed.
3. Forgetting reverse on the DFS solution. Post-order push gives you the order backwards. You must reverse it before returning.
4. Recursion limits in Python. A deep chain of 2,000 prerequisites blows the default recursion depth. Either use Kahn or bump sys.setrecursionlimit.
5. Mixing Kahn and DFS halfway. Pick one approach and stick to it. Combining them silently produces inconsistent answers.

Interview Tips#

• State the algorithm by name. Saying "I will run Kahn algorithm to produce the topological order" sounds far stronger than "I will run BFS."
• Mention multiplicity. Make clear that any valid order is correct. Interviewers do not always emphasize this and a confident note avoids confusion when the grader expects a specific tie-break.
• Build the graph quickly. Two clean lines: append edge and bump in-degree. Do not overthink it.
• Discuss real-world parallels. "This is exactly how npm install resolves package install order" or "This is what make uses to schedule builds" anchors the answer in industry context.

Follow-up Questions#

1. Lexicographically smallest order. Use a min-heap (priority queue) instead of a regular queue in Kahn. That breaks ties by smallest-index-first.
2. Maximum number of parallel semesters. That is LC 1494. Use level-by-level BFS; the number of levels is the answer.
3. All possible topological orders. Backtrack: at each step pick any node with in-degree zero, recurse, undo. Exponential in general.
4. Edges streaming online. Maintain in-degrees incrementally and re-seed the BFS as nodes hit zero.
5. Weighted edges with deadlines. This becomes longest-path-in-DAG, solvable with topological order plus DP in O(V + E).

Key Takeaways#

• Course Schedule II is the canonical topological-sort interview question; learning Kahn is mandatory.
• Edges go prerequisite -> course; reversing direction is the dominant bug.
• Kahn algorithm with in-degrees naturally detects cycles by counting processed nodes.
• DFS post-order also works but requires reversing the result and using three-color cycle detection.
• The output is not unique; any valid order is accepted.
• The pattern underpins build systems, dependency resolvers, schedulers, and migration tools.