~/problems / Graphs / Topological sort (Kahn's)

Course Schedule II

easy ~20 min

Courses are labelled 0 .. num_courses - 1. A pair [a, b] in prerequisites means course b must come before course a.

Write find_order(num_courses, prerequisites) -> list[int] that returns an order containing every course exactly once and respecting every prerequisite. If several orders work, return any of them. If no order exists (there's a cycle), return [].

find_order(2, [[1, 0]])                  # [0, 1]
find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
# [0, 1, 2, 3] or [0, 2, 1, 3]
find_order(2, [[0, 1], [1, 0]])          # []

Constraints: up to 100,000 courses and 150,000 pairs; pairs may repeat. Aim for O(V + E), and avoid recursion deep enough to hit Python's limit.

Topic: Topological sort (Kahn's). BFS over in-degree-0 nodes; leftover nodes mean a cycle.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc