Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Order the vertices of a directed acyclic graph so every edge points forward. Compute each vertex's in-degree, queue all zero in-degree vertices, then repeatedly pop one into the output and decrement its neighbors' in-degrees, queuing any that hit zero. If the output holds fewer than V vertices at the end, the graph had a cycle. O(V + E).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model prerequisites as a directed graph, use in-degrees with a queue, and recognize that an incomplete output signals a cycle.
Where candidates slip
Building edges in the wrong direction (prerequisite vs dependent), or forgetting the cycle check so a cyclic graph silently returns a partial, invalid order.
How to stand out
State the in-degree invariant, explain why an incomplete output means a cycle, and contrast Kahn's BFS with the DFS-postorder variant (and why BFS avoids deep recursion).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Vertices 4 and 5 start with in-degree 0. Edges all point forward in any valid topological order.
How to read it:0 → 1 → 0 loops forever; neither vertex's in-degree can reach zero, so Kahn outputs fewer than V.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
DFS Postorder (Baseline Alternative)
1Hint 1Explore hintHide hint
If you DFS from a vertex and only record it after all its descendants are recorded, every descendant lands before it. What ordering does that give if you reverse the record?
2Hint 2Explore hintHide hint
Maintain three states per node (unvisited, in-progress, done). Finding an in-progress node again means a back edge — a cycle.
3Hint 3Explore hintHide hint
Append each node to a list when its DFS finishes (postorder), then reverse the list for the topological order.
A · Core idea
DFS gives a topological order through postorder: a vertex is finalized only after every vertex it can reach has been finalized.
The idea. Run DFS. When a vertex's exploration completes — all outgoing edges followed — append it to a list. Because every descendant finishes before its ancestor, the ancestors end up later in the postorder list. Reverse that list and every edge u → v now has u before v: a valid topological order.
Cycle detection via coloring. Track three states: unvisited (white), on the current recursion path (gray), and fully done (black). If DFS reaches a gray vertex, we have found a back edge to an ancestor still on the stack — a cycle — so no topological order exists.
Why mention it but often prefer Kahn. DFS postorder is elegant and equally O(V + E), but the natural implementation is recursive. On a graph with 10⁵ vertices arranged in a long chain, the recursion can blow the call stack. You can convert it to an explicit-stack iterative DFS, but at that point Kahn's queue-based BFS is usually cleaner to reason about and reports cycles by a simple count. So this is a strong baseline to state, with Kahn as the iterative answer.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1],[0,2]]Array state
1 finishes
append 1
[0, 2, 1] (a valid order)C · Code with teaching comments
Reference implementation previewpublic int[] topoSortDFS(int n, int[][] edges) { List<Integer>[] adj = new List[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); for (int[] e : edges) adj[e[0]].add(e[1]); Explore the full codeHide the full code
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Two routes to the same destination: DFS reaches it via postorder + reversal, Kahn via in-degree peeling. Knowing both — and that DFS risks deep recursion — lets you justify your choice instead of defaulting blindly.
ComplexityO(V + E) time, O(V + E) space — Every vertex and edge is visited once → O(V + E). The recursion stack and the order list use O(V), adjacency list O(V + E).
E · Edge cases and pitfalls3Recursive DFS can overflow the stack on deep graphs — convert to iterative or use Kahn.Explore edge casesHide edge cases
Pitfalls
- Recursive DFS can overflow the stack on deep graphs — convert to iterative or use Kahn.
- Forgetting to reverse the postorder list.
- Missing the gray-state check, so cycles go undetected.
Approach 2 of 2 · Optimal
Kahn's Algorithm — In-Degree BFS (Optimal)
1Hint 1Explore hintHide hint
A vertex can be placed first only if nothing points into it — in-degree 0. Compute every vertex's in-degree.
2Hint 2Explore hintHide hint
Start a queue with all in-degree-0 vertices. Pop one, append it to the order, and 'remove' it by decrementing each neighbor's in-degree.
3Hint 3Explore hintHide hint
Whenever a neighbor's in-degree drops to 0, all its prerequisites are placed, so enqueue it. If you can't place all V vertices, a cycle blocked you.
A · Core idea
Kahn's algorithm runs a breadth-first traversal driven not by distance but by dependency counts. The indegree[v] of a vertex is the number of edges pointing into it — the number of prerequisites still unplaced.
Setup. Build the directed adjacency list (u → v for each edge) and compute indegree[v] by counting incoming edges. Every vertex with indegree == 0 has no prerequisites, so it is immediately placeable — push all of them into a queue.
The main loop. Pop a vertex u, append it to the output order, and conceptually delete it from the graph: for each outgoing edge u → v, decrement indegree[v]. That decrement says 'one of v's prerequisites is now satisfied'. The moment indegree[v] reaches 0, every prerequisite of v has been placed, so v becomes placeable — enqueue it. Repeat until the queue empties.
Why an incomplete output means a cycle. Every vertex that ever reaches in-degree 0 gets enqueued and then output exactly once. If some vertices never reach 0, they are stuck waiting on a prerequisite that itself is waiting — directly or transitively — on them. That mutual waiting is precisely a directed cycle. So the check is just a count: if order.size() < V, the leftover vertices lie on (or after) a cycle and no topological order exists. This makes Kahn a two-in-one: it produces the order and detects cycles with the same machinery.
Why BFS / iterative, not recursion. The whole algorithm is a while loop over a queue — there is no recursion, so a graph with 10⁵ vertices in a long chain cannot overflow the call stack the way recursive DFS might. That stack safety is a concrete reason to prefer Kahn on large inputs.
The order is one of many. Whichever zero-in-degree vertex the queue hands you first shapes the output. A FIFO queue yields one valid order; a different container yields another. All are correct as long as every edge points forward.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 6, edges = [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]Array state
init
queue = [4, 5]
[4, 5, 2, 0, 3, 1] (6 vertices = V → no cycle)C · Code with teaching comments
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Reframe 'topological sort' as 'repeatedly remove a vertex with no remaining prerequisites'. In-degree counting makes that removal O(1) amortized, and the leftover count after the loop is a free cycle detector. This exact pattern is Course Schedule I/II and Alien Dictionary.
ComplexityO(V + E) time, O(V + E) space — Computing in-degrees scans all E edges. Each vertex is enqueued/dequeued once (O(V)) and each edge is relaxed once when its source is removed (O(E)). Total O(V + E), space O(V + E) for the adjacency list, in-degree array, and queue.
E · Edge cases and pitfalls7no edges, n vertices — All in-degree 0 → every vertex enqueued at start → any permutation is valid.Explore edge casesHide edge cases
Edge cases handled
no edges, n verticesAll in-degree 0 → every vertex enqueued at start → any permutation is valid.self-loop [u, u]indegree[u] never reaches 0 → u is dropped → output short → cycle reported.two-node cycle [[0,1],[1,0]]Neither reaches in-degree 0 → queue empty immediately → return [].
Pitfalls
- Building edges backwards (dependent → prerequisite) reverses or breaks the order.
- Omitting the count == V cycle check, so a cyclic graph returns a bogus partial order.
- Recomputing in-degrees inside the loop instead of decrementing incrementally.
- Decrementing then forgetting to enqueue at exactly zero (off-by-one stalls the BFS).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] topoSortKahn(int n, int[][] edges) { List<Integer>[] adj = new List[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); int[] indegree = new int[n]; for (int[] e : edges) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Edges built backwards
If u → v means 'u before v', the edge and in-degree must point from prerequisite to dependent. Reversing them produces the exact opposite order or a spurious cycle.
Explore the code comparisonHide the code comparison
Edges built backwards
If u → v means 'u before v', the edge and in-degree must point from prerequisite to dependent. Reversing them produces the exact opposite order or a spurious cycle.
Don't write this
for u, v in edges:
adj[v].append(u) # reversed direction
indegree[u] += 1Write this instead
for u, v in edges:
adj[u].append(v) # u is prerequisite of v
indegree[v] += 12No cycle check
When a cycle exists, some vertices never reach in-degree 0 and never enter the output. Returning the partial order pretends a valid ordering exists.
Explore the code comparisonHide the code comparison
No cycle check
When a cycle exists, some vertices never reach in-degree 0 and never enter the output. Returning the partial order pretends a valid ordering exists.
Don't write this
while (!queue.isEmpty()) { /* fill order */ }
return order; // wrong if a cycle left vertices outWrite this instead
while (!queue.isEmpty()) { /* fill order */ }
return idx == n ? order : new int[]{};3Enqueue not gated on zero
Enqueuing a neighbor on every decrement (not only at zero) processes vertices before all prerequisites are placed, breaking the order and double-counting.
Explore the code comparisonHide the code comparison
Enqueue not gated on zero
Enqueuing a neighbor on every decrement (not only at zero) processes vertices before all prerequisites are placed, breaking the order and double-counting.
Don't write this
for v in adj[u]:
indegree[v] -= 1
queue.append(v) # enqueues too early / repeatedlyWrite this instead
for v in adj[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)Revise
Carry the pattern into the interview
Pattern to remember
In-degree BFS — peel off zero-dependency nodes
Code pattern to memorize
compute indegree[v] for all v
queue = all v with indegree[v] == 0
while queue:
u = queue.pop(); order.append(u)
for v in adj[u]:
if --indegree[v] == 0: queue.push(v)
if len(order) < V: cycle existsRules to remember
- 1Process a vertex only when its in-degree hits zero — all prerequisites are done.
- 2Decrement a neighbor's in-degree when you remove its predecessor; queue it at exactly zero.
- 3If fewer than V vertices end up in the output, the graph contains a cycle (no valid order).
- 4Topological order exists only for a DAG — cycles make it impossible.
- 5The order is not unique; any sequence respecting all edges is valid (a queue gives one, a stack/DFS another).
Use this pattern when
- Order tasks under prerequisite/dependency constraints (course schedule, build order)
- Detect a cycle in a **directed** graph (Kahn naturally reports it)
- Linearize a DAG before DP over it (longest path, counting paths)
- Resolve dependency graphs: package installs, compilation units, spreadsheet recalc
Choose another pattern when
- Undirected cycle detection → Union-Find or DFS, not in-degrees
- Shortest path with weights → Dijkstra/Bellman-Ford
- You need ALL topological orders → backtracking, not a single BFS
- Graph is guaranteed a tree/forest → a plain traversal suffices
Interview takeaway
Kahn's algorithm is BFS driven by dependency counts: a vertex is ready the moment its last prerequisite is removed. The 'did we output all V?' check makes it a clean two-in-one — topological order plus cycle detection.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical in-degree BFS for DAG ordering and cycle detection. Reach for it on prerequisite/dependency problems and directed cycle checks. The same skeleton solves Course Schedule I/II, Alien Dictionary, and (layered) Parallel Courses; the DFS-postorder variant is the recursive alternative.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Course SchedulePure cycle detection — return whether a valid order exists (Kahn's count == V).
- Course Schedule IIReturn the actual ordering — this exact Kahn output, or [] on a cycle.
- Alien DictionaryComing soonDerive precedence edges from adjacent words, then topologically sort the letters.
- Parallel CoursesComing soonLayered Kahn's — each BFS level is a semester; the number of levels is the minimum time.