Topological Sort
⏱️ ~3-minute bite · solve the sandbox to master
5-Year-Old Metaphor
— The physical, real-world picture. No jargon.👟 Getting dressed in the morning — socks before shoes, shirt before jacket.
The real-world constraint
You can't put shoes on before socks. You can't wear a jacket before the shirt. Some tasks have hard ordering requirements — a dependency: task B cannot start until task A finishes.
Topological sort finds an order where every task comes after all of its dependencies. Not necessarily a unique order — socks and underwear can go in either order, since neither depends on the other.
The key constraint: no circular dependencies
Imagine: "wear shirt before jacket" AND "wear jacket before shirt." Impossible. Topological sort only works on a DAG — Directed Acyclic Graph. Directed means edges have direction (A depends on B, not vice versa). Acyclic means no loops.
✓ Valid DAG
socks → shoes
shirt → jacket
Order: socks, shirt, shoes, jacket ✓
✗ Cycle = impossible
shirt → jacket
jacket → shirt
Circular dependency ✗
Two algorithms — same result
Kahn's (BFS)
Count "how many tasks depend on me?" (in-degree). Start with zero-dependency tasks. Process them, reduce their dependents' counts. Repeat until empty. Cycle detected if output is shorter than the input.
DFS Post-order
Recurse deep. Only add a task to the output after all tasks it depends on have been added. Reverse the stack at the end. Cycle detected by finding a "gray" (currently-visiting) node.
Where you've already seen this
- Webpack / Rollup — builds your modules in the right order so every import is defined before it's used
- Make / Gradle — compiles only what changed, in dependency order
- npm install — resolves package dependency trees (with cycle detection)
- Spreadsheet formulas — Excel evaluates cells in topological order so every formula reads already-computed values
Interactive Sandbox
— Move something, see it react instantly.Queue (in-degree = 0)
Result so far
Challenge
Explore all 5 patterns — Kahn's BFS, DFS post-order, Course Schedule, Build Order, and Cycle Detection — to master topological sort.
Why Should I Care?
— The exact interview question + the bug it kills.Classic interview question
"There are n courses labeled 0 to n-1. Some courses have prerequisites. Given a list of [course, prerequisite] pairs, return true if you can finish all courses." (LeetCode 207 — Course Schedule)
| 1 | function canFinish(n: number, prereqs: number[][]): boolean { |
| 2 | const inDeg = new Array(n).fill(0); |
| 3 | const adj: number[][] = Array.from({ length: n }, () => []); |
| 4 | |
| 5 | for (const [course, pre] of prereqs) { |
| 6 | adj[pre].push(course); |
| 7 | inDeg[course]++; |
| 8 | } |
| 9 | |
| 10 | const queue = []; |
| 11 | for (let i = 0; i < n; i++) if (inDeg[i] === 0) queue.push(i); |
| 12 | |
| 13 | let processed = 0; |
| 14 | while (queue.length > 0) { |
| 15 | const node = queue.shift()!; |
| 16 | processed++; |
| 17 | for (const neighbor of adj[node]) { |
| 18 | if (--inDeg[neighbor] === 0) queue.push(neighbor); |
| 19 | } |
| 20 | } |
| 21 | return processed === n; // false = cycle exists |
| 22 | } |
| 23 | // Time: O(V + E) · Space: O(V + E) |
Harder follow-up (very common at FAANG)
"Return the order in which to take all courses, or an empty array if impossible." (LeetCode 210 — Course Schedule II)
| 1 | function findOrder(n: number, prereqs: number[][]): number[] { |
| 2 | const inDeg = new Array(n).fill(0); |
| 3 | const adj: number[][] = Array.from({ length: n }, () => []); |
| 4 | for (const [c, p] of prereqs) { adj[p].push(c); inDeg[c]++; } |
| 5 | |
| 6 | const queue = []; |
| 7 | for (let i = 0; i < n; i++) if (inDeg[i] === 0) queue.push(i); |
| 8 | |
| 9 | const order: number[] = []; |
| 10 | while (queue.length > 0) { |
| 11 | const node = queue.shift()!; |
| 12 | order.push(node); |
| 13 | for (const next of adj[node]) |
| 14 | if (--inDeg[next] === 0) queue.push(next); |
| 15 | } |
| 16 | return order.length === n ? order : []; // empty = cycle |
| 17 | } |
Complexity
| Approach | Time | Space |
|---|---|---|
| Kahn's BFS | O(V + E) | O(V + E) |
| DFS Post-order | O(V + E) | O(V) stack |
V = vertices (nodes), E = edges. Both are optimal — you must touch every node and edge at least once.
Production bugs this pattern prevents
- Webpack circular import hang — without topological ordering, a circular import causes the bundler to attempt infinite resolution. Modern bundlers detect the cycle and warn; topo sort is how they know.
- Database migration deadlock — running migrations in the wrong order fails foreign key constraints. CI pipelines sort migrations by dependency graph before applying them.
- Microservice startup race — services that depend on other services must start in order. Kubernetes uses a dependency DAG to sequence pod initialization.
The Deep Dive
— Spec refs, engine internals, the minutiae.Kahn's algorithm — full implementation
| 1 | // Generic Kahn's with adjacency list |
| 2 | function kahnSort<T>(nodes: T[], deps: [T, T][]): T[] | null { |
| 3 | const inDeg = new Map<T, number>(); |
| 4 | const adj = new Map<T, T[]>(); |
| 5 | for (const n of nodes) { inDeg.set(n, 0); adj.set(n, []); } |
| 6 | for (const [from, to] of deps) { |
| 7 | adj.get(from)!.push(to); |
| 8 | inDeg.set(to, inDeg.get(to)! + 1); |
| 9 | } |
| 10 | const queue = nodes.filter(n => inDeg.get(n) === 0); |
| 11 | const result: T[] = []; |
| 12 | while (queue.length > 0) { |
| 13 | const node = queue.shift()!; |
| 14 | result.push(node); |
| 15 | for (const next of adj.get(node)!) { |
| 16 | const d = inDeg.get(next)! - 1; |
| 17 | inDeg.set(next, d); |
| 18 | if (d === 0) queue.push(next); |
| 19 | } |
| 20 | } |
| 21 | return result.length === nodes.length ? result : null; // null = cycle |
| 22 | } |
DFS with 3-color marking (white/gray/black)
White = unvisited, Gray = currently on the DFS call stack (in-progress), Black = fully processed. A back edge to a gray node means a cycle.
| 1 | type Color = "white" | "gray" | "black"; |
| 2 | |
| 3 | function dfsTopoSort(nodes: string[], adj: Record<string, string[]>): string[] | null { |
| 4 | const color: Record<string, Color> = {}; |
| 5 | for (const n of nodes) color[n] = "white"; |
| 6 | const result: string[] = []; |
| 7 | |
| 8 | function dfs(node: string): boolean { |
| 9 | color[node] = "gray"; // mark in-progress |
| 10 | for (const next of adj[node] ?? []) { |
| 11 | if (color[next] === "gray") return false; // back edge = cycle |
| 12 | if (color[next] === "white" && !dfs(next)) return false; |
| 13 | } |
| 14 | color[node] = "black"; // mark done |
| 15 | result.unshift(node); // prepend = reverse post-order |
| 16 | return true; |
| 17 | } |
| 18 | |
| 19 | for (const n of nodes) |
| 20 | if (color[n] === "white" && !dfs(n)) return null; // cycle |
| 21 | |
| 22 | return result; |
| 23 | } |
Lexicographically smallest topological sort
Multiple valid orderings exist whenever some nodes have equal in-degree at the same step. To always pick the lexicographically smallest, replace the queue with a min-heap (priority queue). Every dequeue operation returns the smallest available node. Time becomes O((V + E) log V).
| 1 | // Replace queue.shift() / queue.push() with a MinHeap |
| 2 | // Dequeue = extract-min → always picks smallest ready node |
Counting all topological orderings
The number of distinct valid orderings can be exponential. To count them: backtrack — at each step, try all in-degree-0 nodes, recurse, undo. Time O(answer × (V + E)) — only feasible for small graphs. For large graphs this is a #P-complete problem.
Strongly Connected Components (Tarjan's / Kosaraju's)
In a directed graph with cycles, SCCs are maximal sets of nodes where every node is reachable from every other. Collapsing each SCC into a single "super node" produces a DAG — which you can then topologically sort. This is how compilers resolve mutually-recursive modules: detect SCCs (mutual dependencies), compile each SCC as a unit, then sort the DAG of units.
- Tarjan's — single DFS pass, O(V + E). Uses a stack and low-link values to find SCCs on the fly.
- Kosaraju's — two DFS passes. Pass 1: DFS on original graph, push finish order to a stack. Pass 2: DFS on transposed graph in reverse finish order. Each tree in pass 2 is one SCC.
Related patterns to know next
- BFS / Shortest path on DAGs — topo sort first, then relax edges in order for O(V + E) shortest path (faster than Dijkstra on DAGs)
- Dynamic programming on DAGs — longest path, counting paths, and critical path (used in project scheduling) all reduce to DP evaluated in topological order
- Union-Find for cycle detection — undirected graph variant; simpler than DFS coloring but only handles undirected cycles
Interview Questions
— Real questions from real interviews — with answers.Linear ordering of nodes such that every directed edge u→v has u before v — only possible on DAGs (no cycles).
Kahn's uses in-degrees and a queue — naturally detects cycles; DFS uses post-order and a stack — more intuitive from recursion.
If the number of nodes processed is less than n, a cycle exists — those nodes never reached in-degree 0.
Topological order first, then relax edges in that order — O(V+E) vs Dijkstra's O((V+E) log V) for general graphs.
Build a directed graph, run topological sort — if output size equals n, it's possible; otherwise, there's a cycle.
Memory Game
— Quick quiz — lock the concept in long-term memory.What is the 'number of ways to reorder array to get the same BST' problem's topological component?