Course Schedule II — InterviewPrepKit

Solving tips

Recognize this as topological sort: same graph as Course Schedule (edge b -> a for [a,b]), now outputting an actual order that exists iff the graph is acyclic.
Kahn's BFS builds the answer directly — append each course as its in-degree hits 0; if fewer than numCourses come out, a cycle trapped the rest, so return [].
DFS alternative: append nodes at finish time (post-order) then REVERSE the list; forgetting the reverse gives the opposite (invalid) order.
Both O(V+E); return the empty-list sentinel on a cycle rather than a partial order, and mind the edge direction.

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.

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 [].

class Solution:
    def findOrder(self, 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 rescanning all prerequisites → O(V · E). 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 trapped the rest — return [].

from collections import deque


class Solution:
    def findOrder(self, 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.

class Solution:
    def findOrder(self, 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 your cycle check is your impossibility check — return the sentinel when the count falls short.