Course Schedule II (topo)

Signal

"Produce a valid order that respects a bunch of before/after dependencies, or detect that it's impossible" is topological sort — and "impossible" always means a cycle in the dependency graph.

Approach

Build a graph of prerequisite → course edges and count each course's in-degree (how many prerequisites it still needs). Start a queue with every course that has in-degree 0 (no prerequisites left). Repeatedly pop a course, append it to the order, and decrement the in-degree of everything it unlocks — enqueueing any course that drops to 0. If the final order includes every course, it's valid; if it's short, the remaining courses are stuck in a cycle.

Skeleton

graph = adjacency list, indeg = in-degree count per course
queue = all courses with indeg == 0
order = []
while queue:
    c = queue.pop()
    order.append(c)
    for next_course in graph[c]:
        indeg[next_course] -= 1
        if indeg[next_course] == 0: queue.push(next_course)
return order if len(order) == num_courses else []

Solution

from collections import deque

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    order: list[int] = []

    while queue:
        c = queue.popleft()
        order.append(c)
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

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

Complexity

O(V + E) time — each course and each prerequisite edge is processed once. O(V + E) space for the graph and in-degree tracking.

Pitfalls

• Getting the edge direction backwards (course -> prereq instead of prereq -> course) inverts the whole algorithm and produces a wrong or reversed order.
• Checking len(order) == num_courses is the only correct way to detect a cycle here — a cyclic subset of courses never reaches in-degree 0, so they simply never enter the queue, silently missing from order.
• This is the same graph as the boolean "Course Schedule" question, just returning the order instead of a yes/no — recognize you can reuse the exact same Kahn's-algorithm scaffold for both.