Problem 42 · Graphs

Course Schedule II (Topological Sort)

MediumClassic DSA & systems

01Problem

Given numCourses and prerequisite pairs [course, prereq], return any valid order to take all courses, or an empty list if a cycle makes it impossible.

02Key insight

Kahn's algorithm: repeatedly take nodes with in-degree zero. If fewer than n nodes are emitted, the remainder form at least one cycle.

03Solution

solution.pypython18 lines

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(i for i in range(num_courses) if indegree[i] == 0)
    order: list[int] = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == num_courses else []

Try it first.

TimeO(V+E)

SpaceO(V+E)

tests.py · 4 passing

tests.pypython5 lines

assert find_order(2, [[1, 0]]) == [0, 1]
assert find_order(2, [[1, 0], [0, 1]]) == []
o = find_order(4, [[1,0],[2,0],[3,1],[3,2]])
assert o[0] == 0 and o[-1] == 3 and len(o) == 4
assert find_order(1, []) == [0]

04Staff-level follow-up

How would you schedule a DAG of jobs in parallel (e.g. Spark stages)? Process Kahn's queue level by level; each level's jobs run concurrently and the level count is the critical-path length.