Course Schedule II: Topological Sort with BFS

You are given numCourses and a list of prerequisite pairs. Each pair [a, b] means you must take course b before course a. Return an ordering of courses you can take to finish them all. If no valid ordering exists (because of a cycle), return an empty array.

This is LeetCode 210: Course Schedule II, and it is the natural follow-up to Course Schedule. In that problem you only needed a yes/no answer: can you finish all courses? Here you need to produce the actual ordering. That means you need topological sort, not just cycle detection.

Prerequisites: [1,0], [2,0], [3,1], [3,2]

Valid ordering:[0, 1, 2, 3]or[0, 2, 1, 3]

Why this problem matters

Topological sort is one of the most practically useful graph algorithms. Every time you run npm install, the package manager resolves a dependency graph and installs packages in topological order. Build systems like Make and Gradle do the same thing to decide which targets to compile first. If you have ever debugged a circular dependency error, you have encountered the failure mode of topological sort.

In interviews, Course Schedule II is the canonical topological sort problem. It tests whether you can translate a list of dependency pairs into a directed graph, then extract a valid ordering using BFS or DFS. The graph construction step alone trips up many candidates who mix up edge directions.

Understanding this problem also unlocks a family of harder problems. Alien Dictionary asks you to infer character ordering constraints and then topological sort them. Parallel Courses layers on level tracking. Once you have Kahn's algorithm in muscle memory, these extensions become manageable.

Thinking it through

The input gives you pairs like [1, 0], meaning "to take course 1, you must first complete course 0." Model each course as a node and draw a directed edge from 0 to 1 (the prerequisite points to the course that depends on it). Now you have a directed graph, and you need to find an ordering where every node appears after all of its predecessors.

That is exactly what topological sort does. If the graph has a cycle, no such ordering exists and you return []. If it is a DAG (directed acyclic graph), at least one valid ordering exists.

Two classic approaches:

1. BFS (Kahn's algorithm): peel off nodes with zero in-degree, layer by layer
2. DFS with reverse post-order: recurse through all descendants first, then record the node

Both produce a valid topological ordering in O(V + E) time.

BFS approach: Kahn's algorithm

Kahn's algorithm builds the ordering from the front. The idea is simple: any course with no remaining prerequisites can be taken right now. Take it, remove its edges, and see what new courses become available.

Here is the algorithm:

1. Build an adjacency list and compute the in-degree (number of incoming edges) for every course
2. Add every course with in-degree 0 to a queue
3. While the queue is not empty: dequeue a course, append it to the result, and decrement the in-degree of all its neighbors
4. When a neighbor's in-degree drops to 0, add it to the queue
5. If the result contains all courses, return it. Otherwise, a cycle exists and you return []

from collections import deque

def findOrder(numCourses, prerequisites):
    graph = {i: [] for i in range(numCourses)}
    in_degree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1

    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) == numCourses:
        return order
    return []

The key difference from Course Schedule I is that you collect the actual ordering instead of just counting processed nodes. Every time you dequeue a course, you append it to the result. At the end, if the result length matches numCourses, you have a valid schedule.

DFS approach

The DFS approach builds the ordering from the back. You recurse through a node's entire subtree first, then record the node. This produces a reverse topological order, so you reverse it at the end.

You also need cycle detection. Use three states: unvisited (0), visiting (1), and visited (2). If DFS reaches a node that is currently in the "visiting" state, you have found a back edge and the graph has a cycle.

def findOrder(numCourses, prerequisites):
    graph = {i: [] for i in range(numCourses)}
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    state = [0] * numCourses
    order = []
    has_cycle = False

    def dfs(node):
        nonlocal has_cycle
        if has_cycle:
            return
        state[node] = 1

        for neighbor in graph[node]:
            if state[neighbor] == 1:
                has_cycle = True
                return
            if state[neighbor] == 0:
                dfs(neighbor)

        state[node] = 2
        order.append(node)

    for i in range(numCourses):
        if state[i] == 0:
            dfs(i)

    if has_cycle:
        return []
    return order[::-1]

The DFS approach appends each node after processing all its descendants, which gives reverse topological order. The final order[::-1] flips it to the correct direction.

Complexity analysis

V is the number of courses, E is the number of prerequisite pairs.

Time: Both approaches visit every node and edge exactly once. Building the adjacency list takes O(E), and the traversal takes O(V + E).

Space: The adjacency list uses O(V + E). Kahn's uses O(V) for the in-degree array and O(V) for the queue. DFS uses O(V) for the state array and O(V) for the recursion stack. Total is O(V + E) for both.

Edge cases to watch for

• No prerequisites: every course is independent. Any permutation is valid. Kahn's starts with all nodes in the queue and dequeues them in order.
• Cycle in the graph: [[1,0],[0,1]] means course 0 needs 1 and course 1 needs 0. No valid ordering. Return [].
• Single course: numCourses = 1, prerequisites = []. Return [0].
• Linear chain: prerequisites form a single path like 0 to 1 to 2 to 3. Only one valid ordering exists.
• Disconnected components: multiple independent groups of courses. Both approaches handle this naturally since they iterate over all nodes.
• Multiple valid orderings: the problem accepts any valid topological sort, so you do not need to find a specific one.

The building blocks

This problem combines two reusable patterns that CodeBricks drills independently:

1. Adjacency list construction with in-degree tracking

The setup step is shared with many graph problems, but Course Schedule II adds the in-degree array:

graph = {i: [] for i in range(n)}
in_degree = [0] * n
for course, prereq in prerequisites:
    graph[prereq].append(course)
    in_degree[course] += 1

Getting the edge direction right is critical. The pair [course, prereq] means prereq must come before course, so the edge goes from prereq to course. The in-degree of course increases because it has one more incoming dependency.

2. BFS peel-off loop (Kahn's pattern)

The core loop is a BFS that processes nodes in dependency order:

queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

This pattern shows up in any problem where you need to process items in dependency order. You start with items that have no dependencies, process them, and unlock new items as their dependency counts drop to zero. It is the same pattern behind Parallel Courses and Minimum Height Trees.

From understanding to recall

You have seen both Kahn's BFS and DFS approaches for producing a topological ordering. The logic makes sense when reading through it. But in an interview, you need to reconstruct the adjacency list setup, the in-degree computation, the BFS loop, and the final length check, all from memory and under time pressure.

The gap between "I understand it" and "I can write it cold" is exactly what spaced repetition closes. You practice building the adjacency list and writing the Kahn's loop from scratch at increasing intervals. After a few rounds, the pattern becomes automatic. You stop thinking about which direction the edges go because your hands already know.

Related posts

• Course Schedule - The prerequisite (pun intended) to this problem, checking if ordering is possible
• Number of Islands - The essential graph traversal problem, teaching BFS and DFS on implicit graphs
• Clone Graph - Another graph problem requiring adjacency list traversal with visited tracking
• Alien Dictionary - A harder topological sort problem where you must infer the graph from character ordering constraints