Course Schedule II — InterviewPrepKit

Problem

There are numCourses courses labeled 0 to numCourses - 1. Each prerequisites[i] = [a, b] means course b must be taken before course a.

Return any valid order in which you can take all the courses. If no valid order exists (a circular dependency makes it impossible), return the empty list [].

This is Course Schedule I, but instead of a yes/no you must produce an actual ordering.

Examples

numCourses = 2, prerequisites = [[1,0]] → [0, 1] — 0 has no prerequisite, and 1 needs 0.
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] → [0, 1, 2, 3] — 0 first, then 1 and 2 (either order), then 3. [0, 2, 1, 3] is equally valid.
numCourses = 1, prerequisites = [] → [0] — one course, nothing blocks it.
numCourses = 2, prerequisites = [[1,0],[0,1]] → [] — cyclic, impossible.

The second example as a dependency graph, where an arrow means “must be taken before”:

flowchart TD
    C0["Course 0"] --> C1["Course 1"]
    C0 --> C2["Course 2"]
    C1 --> C3["Course 3"]
    C2 --> C3

Any order that lists every course after its prerequisites is valid, so both [0, 1, 2, 3] and [0, 2, 1, 3] work.

Constraints

1 <= numCourses <= 2000
0 <= len(prerequisites) <= numCourses * (numCourses - 1)
Each prerequisites[i] is a pair of distinct labels; no duplicate pairs.

Think about it first

Hint 1

Same graph as Course Schedule: edge b → a for each [a, b]. You now need to output a linear ordering that respects every edge — a topological sort. It exists iff the graph is acyclic.

Hint 2

Kahn's algorithm builds the order directly: courses become "ready" the moment their in-degree hits 0. Append each course to the answer as you take it. If a cycle blocks some courses, you'll take fewer than numCourses — detect that and return [].

Hint 3

DFS alternative: the reverse of a DFS post-order (finish order) is a valid topological order. Add three-color cycle detection so you can bail out with [] when a back edge appears.

TL;DR

Topological sort of the prerequisite graph — Kahn’s BFS emits the order directly (or DFS reverse post-order), both O(V + E) time and space; return [] on a cycle.

Approach 1 — Brute force (repeatedly append any takeable course)

Naively: keep scanning for a not-yet-taken course whose prerequisites are all taken, append it, repeat until a full pass makes no progress. If you took everyone, return the order; otherwise return [].

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    taken = [False] * numCourses
    order = []
    while True:
        progressed = False
        for course in range(numCourses):
            if taken[course]:
                continue
            if all(taken[b] for a, b in prerequisites if a == course):
                taken[course] = True
                order.append(course)
                progressed = True
        if not progressed:
            break
    return order if len(order) == numCourses else []

Complexity: up to numCourses passes; each pass tests every not-yet-taken course, and each test rescans the whole prerequisite list → O(V² · E) worst case (a reverse chain forces one course per pass). This is Kahn’s algorithm with the in-degree bookkeeping thrown away; restore it to get linear time.

Approach 2 — Kahn’s algorithm (BFS topological sort)

The insight: a course is safe to place next exactly when its in-degree is 0 (all prerequisites already placed). Maintain a queue of such courses; each time you place one, decrement its dependents and enqueue any that reach 0. The append order is itself a valid topological order. If fewer than numCourses courses come out, a cycle blocked the rest, so return [].

from collections import deque


def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    adj = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for a, b in prerequisites:      # edge b -> a
        adj[b].append(a)
        indegree[a] += 1

    queue = deque(c for c in range(numCourses) if indegree[c] == 0)
    order = []
    while queue:
        course = queue.popleft()
        order.append(course)
        for nxt in adj[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

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

Walkthrough (numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]):

Edges 0→1, 0→2, 1→3, 2→3. In-degrees 0:0, 1:1, 2:1, 3:2. Queue [0].
Take 0 → order=[0]; 1 and 2 drop to 0, enqueue → queue [1,2].
Take 1 → order=[0,1]; 3 drops to 1. Take 2 → order=[0,1,2]; 3 drops to 0, enqueue.
Take 3 → order=[0,1,2,3]. Length 4 = numCourses → return [0,1,2,3].

Complexity: O(V + E) time, O(V + E) space.

Approach 3 — DFS reverse post-order

The insight: in a DFS, a node is finished only after all nodes it points to are finished. So if you append each node at the moment it finishes (post-order) and then reverse the list, every edge u → v has u appearing before v — a topological order. Three-color state catches back edges (cycles) so you can abort with []. Prefer DFS when you already think recursively about the graph; prefer Kahn’s when recursion depth (up to 2000) is a concern.

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

    WHITE, GRAY, BLACK = 0, 1, 2
    state = [WHITE] * numCourses
    post = []

    def dfs(course: int) -> bool:
        state[course] = GRAY
        for nxt in adj[course]:
            if state[nxt] == GRAY:
                return False                 # back edge → cycle
            if state[nxt] == WHITE and not dfs(nxt):
                return False
        state[course] = BLACK
        post.append(course)                  # finished after all successors
        return True

    for c in range(numCourses):
        if state[c] == WHITE and not dfs(c):
            return []
    post.reverse()
    return post

Walkthrough (same 4-course example): DFS from 0 recurses 0→1→3 (3 finishes first: post=[3]), back up 1 finishes (post=[3,1]), then 0’s other edge to 2 → 3 already BLACK, 2 finishes (post=[3,1,2]), 0 finishes (post=[3,1,2,0]). Reversed → [0,2,1,3], a valid order.

Complexity: O(V + E) time, O(V + E) space.

Common pitfalls

Forgetting to reverse the DFS post-order — the un-reversed list is the opposite of a valid order.
Returning the partial order on a cycle instead of []; always compare len(order) == numCourses first.
Mixing up edge direction: [a, b] is b → a. Reversed edges yield a reversed (invalid) topological sort.
A visited set that doesn’t separate GRAY from BLACK in DFS misses cycles or, worse, reports false ones.

Pattern takeaway

When a problem asks for an ordering consistent with “must-come-before” constraints, it’s a topological sort. Kahn’s BFS grows the answer as in-degrees reach 0; DFS reverse post-order builds it from finish times. Existence of any valid order equals acyclicity, so the cycle check is the impossibility check: return [] when the count falls short.