Topological sort (Kahn's)

46 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four courses: 0 has no prerequisite; 1 needs 0; 2 needs 0; 3 needs both 1 and 2. In what order can you take them? By hand you say "0 has nothing before it, so take 0 first. Now 1 and 2 are free, take them. Now 3 is free." You never wrote a rule, but you used one: take something that has nothing left waiting on it.

With 4 courses you can see what is free. With 5,000 courses and 20,000 prerequisites you cannot see it, and if you rescan the whole list every time you take a course that is 5,000 × 20,000 = 100 million checks. We want to keep the "how many prerequisites are still waiting" number for every course and update it cheaply.

Build the structure, one piece at a time

First, store the arrows: for each course, the list of courses that need it. 0: [1, 2], 1: [3], 2: [3], 3: [].

Second, a counter per course called its in-degree: how many arrows point into it, that is, how many prerequisites it still has. Count once at the start:

Third, a queue of courses whose in-degree is 0. These can be taken right now. Start: queue = [0].

Now the loop. Take 0 from the queue and write it to the output. For every arrow out of 0, lower the target's counter by one, because one of its prerequisites is now done. 1 drops to 0, so enqueue it; 2 drops to 0, so enqueue it. Queue = [1, 2], output = [0]. Take 1: arrow 1 → 3 lowers 3 to 1, still waiting. Take 2: arrow 2 → 3 lowers 3 to 0, enqueue it. Take 3. Output = [0, 1, 2, 3].

If the prerequisites contain a loop, every course in the loop keeps a counter of at least 1 forever, because each is waiting for another member of the loop. The queue runs dry with courses left over. That is how the same loop also detects cycles: fewer than V courses in the output means a cycle.

Why it is correct

The invariant: a course is in the queue only when its counter is 0, and its counter is 0 only when every prerequisite has already been written to the output. Each decrement happens exactly when a prerequisite is written, so the counter always equals the number of prerequisites not yet output. A course therefore never appears before anything it needs, which is the definition of a valid order.

Why it is fast

Counting in-degrees looks at each arrow once. The loop writes each course once and, when writing it, touches each of its outgoing arrows once. So:

work = V + E

For 5,000 courses and 20,000 prerequisites that is 25,000 steps instead of 100 million rescans.

How to recognise it in an interview

Cues: "order such that every dependency comes first", "build order", "which words come before which" in an unknown alphabet, "can all be done". The first thing to say: "count in-degrees, queue the zeros, and peel." Course Schedule II asks for the order itself; this output list is the answer. Alien Dictionary first turns adjacent words into arrows between letters, then runs exactly this peel. Minimum Height Trees peels leaves (degree 1) layer by layer with the same queue idea.

02The idea in one line

Queue every zero in-degree node; removing it may free its successors.

Reach for it when: Course schedule II, alien dictionary, parallel courses, recipes, longest path in DAG.

Cost: O(V + E) time.

03The walk-through, step by step

The video works one example: Course Schedule II on 4 courses. These are its captions in order, so you can follow without the video or check a step you missed.

1. Count in-degrees: how many prerequisites each course still has
2. Courses with in-degree 0 can start now: queue them
3. Take 0 from the queue: all its prerequisites are done
4. Edge 0→1: in-degree of 1 drops to 0, enqueue it
5. Edge 0→2: in-degree of 2 drops to 0, enqueue it
6. Take 1 from the queue: all its prerequisites are done
7. Edge 1→3: in-degree of 3 drops to 1, still waiting
8. Take 2 from the queue: all its prerequisites are done
9. Edge 2→3: in-degree of 3 drops to 0, enqueue it
10. Take 3 from the queue: all its prerequisites are done
11. All 4 courses taken: order 0, 1, 2, 3 (a cycle would leave some behind)
12. Each edge is relaxed once: O(V + E)

04Asked at Google

11 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).