Course Schedule II — Return a Valid Topological Order with Kahn's BFS

Problem Statement#

There are numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any. If it is impossible to finish all courses, return an empty array.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• All pairs are distinct.

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

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]   // or [0,1,2,3]; any valid order is accepted

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

Why This Problem Matters#

LeetCode 210 Course Schedule II is the bigger sibling of LC 207 and one of the most loved interview questions at Amazon, Google, Meta, and Microsoft. Where LC 207 asks "is it possible?", LC 210 asks "give me a working schedule," which forces the candidate to actually produce a topological order, not just detect a cycle.

The pattern shows up in:

• CI/CD pipelines: order in which tasks must run.
• Spreadsheet recalculation: order of cell updates.
• Symbolic execution and static analysis: dependency ordering.
• Compiler passes: which optimization runs before which.

Acing LC 210 demonstrates that you can produce — not merely verify — a valid linearization of a DAG. That is the same skill required for Alien Dictionary, Parallel Courses, and Build System scheduling.

The Core Insight#

Kahn's algorithm gives you a topological order for free:

1. Build a directed graph with edges prereq -> course.
2. Compute the indegree of every node.
3. Initialize a queue with all indegree-zero nodes.
4. Pop a node, append it to your order list, and decrement indegrees of its neighbors. Push any neighbor whose indegree just hit 0.
5. If at the end len(order) != numCourses, the graph has a cycle — return []. Otherwise return order.

DFS post-order is the other classic technique. After the DFS visits all descendants of a node, push the node onto a stack. Reversing the stack yields a valid topological order. Cycle detection requires a three-color marker.

Both run in O(V + E) time and space. Kahn's BFS is preferred in interviews for two reasons:

• It naturally outputs a level-by-level order that is easier to reason about.
• It avoids recursion stack issues for deep DAGs.

Visual Dry Run#

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]].

Edges: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. Indegrees: [0,1,1,2].

Final order = [0, 1, 2, 3]. Length equals 4, no cycle. The exact order between 1 and 2 is interchangeable because they are siblings; either is accepted.

Solution (Optimal)#

# Python — Kahn's algorithm BFS, O(V+E) time, O(V+E) space
from collections import deque, defaultdict
 
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    indegree = [0] * numCourses
 
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1
 
    queue = deque(i for i in range(numCourses) if indegree[i] == 0)
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
 
    return order if len(order) == numCourses else []

// JavaScript — Kahn's algorithm BFS, O(V+E) time, O(V+E) space
function findOrder(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);
 
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
        indegree[course]++;
    }
 
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
 
    const order = [];
    while (queue.length) {
        const node = queue.shift();
        order.push(node);
        for (const nxt of graph[node]) {
            if (--indegree[nxt] === 0) queue.push(nxt);
        }
    }
 
    return order.length === numCourses ? order : [];
}

# Python — DFS post-order with three-color cycle detection, O(V+E) time, O(V+E) space
def findOrderDFS(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
 
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * numCourses
    order = []
    has_cycle = [False]
 
    def dfs(node: int) -> None:
        if has_cycle[0] or color[node] == BLACK:
            return
        if color[node] == GRAY:
            has_cycle[0] = True
            return
        color[node] = GRAY
        for nxt in graph[node]:
            dfs(nxt)
        color[node] = BLACK
        order.append(node)
 
    for i in range(numCourses):
        if color[i] == WHITE:
            dfs(i)
 
    return order[::-1] if not has_cycle[0] else []

Complexity:

Common Mistakes#

1. Returning the order with the cycle silently included. Always check len(order) == numCourses before returning. A cycle leaves some nodes with indegree > 0 and they never get popped.

2. Forgetting to reverse DFS post-order. Post-order alone gives reverse topological order. The final list must be reversed.

3. Mutating shared indegree between approaches. If you run both BFS and DFS in the same function for some reason, recompute indegrees — Kahn's algorithm consumes them.

4. Using a Python set as the queue. The order becomes nondeterministic. Use deque for stable, predictable behavior.

5. Building edges as course -> prereq instead of prereq -> course. That reversal still detects cycles but produces a reverse topological order.

Interview Tips#

• Open by identifying the problem: "Topological sort on a DAG. Kahn's BFS produces a valid order in O(V + E)."
• After writing Kahn's algorithm, explicitly walk through the cycle case so the interviewer sees you handle invalid input.
• Mention DFS post-order as an alternative and explain when each is preferable: BFS for level-order semantics and parallel scheduling; DFS for compact recursive code.
• If the interviewer pushes for an even more advanced variant, mention LC 269 Alien Dictionary (topological sort with character ordering) and LC 1136 Parallel Courses.

Follow-up Questions#

1. Parallel Courses (LC 1136 / 2050). Minimum semesters if you can take many courses in parallel each semester. Run Kahn's BFS but increment a level counter every time the queue advances.
2. Lexicographically smallest topological order. Replace the deque with a heapq min-heap so the smallest indegree-zero node is always picked first.
3. All valid topological orders. Use backtracking; pick any indegree-zero node, recurse, then undo.
4. Alien Dictionary (LC 269). Derive character precedence from word ordering and run topological sort.
5. Detect specific cycle. When a cycle is detected, return the cycle nodes — useful for debugging build systems.

Key Takeaways#

• Course Schedule II asks for a valid topological order; Kahn's BFS algorithm produces one as a natural byproduct of cycle detection.
• Use a queue (FIFO) and an indegree array — the queue pops nodes whose prerequisites are all satisfied.
• After the BFS, compare len(order) to numCourses to detect cycles. If they differ, return [].
• DFS post-order with three-color marking is the equivalent recursive solution; reverse the post-order list.
• Both approaches are O(V + E) and O(V + E) — optimal because every edge must be inspected at least once.
• The same template handles parallel scheduling, lexicographic order (swap the queue for a heap), Alien Dictionary, and any dependency resolution problem.