Topological Sort¶
Also known as: Kahn's Algorithm, Dependency Ordering, DAG Ordering
Repeatedly take any node with nothing left blocking it, remove it, and see what that unblocks. The order things come out is a valid order to do them in. If you get stuck with nodes remaining, they're waiting on each other — you've found a cycle.
Before you start¶
What 'solved properly' looks like
Target: O(V + E). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You start by counting how many incoming edges (dependencies) each node has. Every node with zero in-degree has nothing blocking it, so it goes first into a queue. You process the queue: for each node, you remove it (add it to the sorted order) and decrement the in-degree of every node that depends on it. Any neighbour whose in-degree hits zero joins the queue. If you finish with all nodes processed, you have a valid order. If some remain, the graph has a cycle.
Why it matters: It's how build systems, package managers, and course prerequisites work, and the fact that failure means "there's a circular dependency" is usually the actual question being asked. Course Schedule problems are among the most common Medium graph questions.
When to reach for it¶
Reach for it when you see prerequisites, build or task ordering, "can you finish all the courses", cycle detection in a directed graph, or scheduling with dependencies.
When not to use it
It only works on a DAG — if there's a cycle, no valid order exists, and half these problems are really asking you to detect exactly that. The in-degree bookkeeping (decrement only when you remove a node, never before) is where the bugs live.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Course Schedule | LeetCode | Medium | 25 mins | teaching |
| 2 | Course Schedule II | LeetCode | Medium | 25 mins | teaching |
| 3 | Find Eventual Safe States | LeetCode | Medium | 30 mins | consolidation |
| 4 | Minimum Height Trees | LeetCode | Medium | 35 mins | challenge |
Already know this? Test out.
If you can solve Course Schedule II cleanly in one sitting — building the full order by repeatedly taking a node with zero remaining dependencies — you already own this pattern, so move on to the next one. If it tangles you up on cycles or ordering, that's your signal to work the set from the top instead of skipping.