Course Schedule II

Difficulty: Medium Source: NeetCode

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

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 = 2, prerequisites = [[1,0]] Output: [0,1]

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

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• All pairs are unique, no self-loops

Prerequisites

Before attempting this problem, you should be comfortable with:

• Course Schedule I (LeetCode 207) — the cycle detection version of this problem
• Topological sort — ordering nodes in a DAG such that all prerequisites come before dependents
• Kahn’s algorithm (BFS) — the standard iterative approach to topological sorting

1. DFS Topological Sort

Intuition

DFS-based topological sort: run DFS on each node, and after fully exploring all of a node’s descendants, add it to the front of the result. This is because in a topological order, a node must come before all nodes it points to — so once we know all “after” nodes are processed, we can place the current node.

Use three states to detect cycles: 0 = unvisited, 1 = in-stack, 2 = done. If we hit a 1 state, there’s a cycle — return [].

Algorithm

1. Build the adjacency list.
2. For each unvisited node, run DFS. Append to order after all children are processed.
3. If a cycle is detected at any point, return [].
4. Return order reversed (since we append post-order).

Solution

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[b].append(a)

    state = [0] * numCourses  # 0=unvisited, 1=in-stack, 2=done
    order = []

    def dfs(node):
        if state[node] == 1:
            return False  # cycle
        if state[node] == 2:
            return True   # already processed
        state[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        state[node] = 2
        order.append(node)
        return True

    for course in range(numCourses):
        if not dfs(course):
            return []

    return order[::-1]  # reverse post-order = topological order


print(findOrder(2, [[1,0]]))                           # [0, 1]
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))         # [0, 1, 2, 3] or [0, 2, 1, 3]
print(findOrder(2, [[1,0],[0,1]]))                     # [] (cycle)
print(findOrder(1, []))                                # [0]

Complexity

• Time: O(V + E)
• Space: O(V + E) for graph, state array, and order list

2. Kahn’s Algorithm (BFS Topological Sort)

Intuition

Kahn’s algorithm builds the topological order iteratively. Nodes with in-degree 0 have no prerequisites — they can be taken first. Remove them, decrement their neighbors’ in-degrees, and enqueue any neighbor that now has in-degree 0. The order in which nodes are dequeued is a valid topological ordering. If we can’t process all nodes, there’s a cycle.

Algorithm

1. Compute in-degrees. Enqueue all nodes with in-degree 0.
2. While queue is non-empty: dequeue course, add to order. For each neighbor, decrement in-degree; if 0, enqueue.
3. Return order if len(order) == numCourses, else [].

Solution

from collections import deque

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses

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

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

    while queue:
        course = queue.popleft()
        order.append(course)
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

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


print(findOrder(2, [[1,0]]))                           # [0, 1]
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))         # [0, 2, 1, 3] (one valid order)
print(findOrder(2, [[1,0],[0,1]]))                     # []
print(findOrder(3, []))                                # [0, 1, 2] (any order)

Complexity

• Time: O(V + E)
• Space: O(V + E)

Common Pitfalls

DFS: appending before all children are processed. In DFS topological sort, you append the node to order after the recursive call returns (post-order), not before. Pre-order would give you the wrong order.

Reversing the DFS result. DFS appends nodes in reverse topological order (last course first), so you need order[::-1]. Kahn’s BFS naturally gives the correct forward order.

Checking len(order) == numCourses. This is how you detect cycles in Kahn’s algorithm. If a cycle exists, some nodes will never reach in-degree 0 and will never be added to order.