What Is Topological Sort? The Coding Interview Guide

Your build system has seventeen steps. Step 3 needs Step 7. Step 7 needs Step 12. Step 12 needs Step 3. Nothing compiles. Nobody knows why. This is a Tuesday.

Topological sort is the algorithm that prevents this. It takes a directed acyclic graph where edges mean "this before that" and returns a linear sequence where every dependency is satisfied. Order from chaos. Not glamorous. Absolutely necessary.

If you have bumped into course prerequisite problems on LeetCode, or stared at a "find a valid build order" question in a coding interview, you have already met this algorithm. You just did not know its name.

Your Dependencies Have Opinions

Imagine five college courses. Some require others first.

Course 0: no prerequisites
Course 1: requires Course 0
Course 2: requires Course 0
Course 3: requires Courses 1 and 2
Course 4: requires Course 3

One valid order: 0, 1, 2, 3, 4. Another: 0, 2, 1, 3, 4. Both work. The algorithm does not care which one you return, and neither does the interviewer, as long as all dependencies are respected.

A topological ordering is any sequence of nodes where every directed edge u → v has u appearing before v. The algorithm finds "a" valid ordering, not "the" ordering. Multiple correct answers usually exist, which is already more flexible than most real-world dependency systems (looking at you, npm).

This works on directed acyclic graphs (DAGs). The edges have direction (A requires B, not vice versa) and there are no cycles. The "acyclic" part is not a minor implementation detail. It is foundational, and violating it makes the problem unsolvable.

Cycles: The Universe Breaks

Suppose course A requires course B and course B requires course A. Which one do you take first?

You cannot. There is no valid ordering. The problem has no solution. This is also the architectural history of every large software project after its third birthday.

A circular dependency makes topological sort impossible. Not hard. Impossible. No algorithm can produce an ordering that satisfies a requirement that loops back on itself.

If you run topological sort and cycle detection together, you get both a valid ordering and a guarantee that one exists. That is what LeetCode 207 (Course Schedule) is actually testing. The course framing is decoration. The real question is: can you detect a cycle in a directed graph? Return the ordering if not, return empty if yes.

The practical upside: a cycle means no valid build order exists, so returning early is the correct answer, not a failure case. Your algorithm is supposed to refuse.

Two Algorithms, One Problem: Pick One

Two standard algorithms for topological sort. Both run in O(V + E). Neither is wrong. An interviewer will accept either.

Kahn's algorithm (BFS-based): count incoming edges per node, start from nodes with zero, peel the graph layer by layer like an onion that does not make you cry.

DFS-based: do a depth-first traversal, push each node onto a stack after its entire subtree is explored, read the stack in reverse.

Both correct. For interviews, Kahn's tends to be easier to explain while someone watches you write it. The logic is intuitive: start with what has no dependencies, work outward. The DFS version requires keeping a three-color state machine in your head, which is less obvious and easier to blank on under pressure.

Unless you have a strong reason to prefer DFS, go with Kahn's.

Kahn's Algorithm: Start From Zero

A node with no incoming edges has no unmet dependencies. It can go first. After you process it, decrement the in-degree of its neighbors. If any neighbor drops to zero, enqueue it. Repeat until done.

from collections import deque

def topological_sort(num_nodes: int, edges: list[tuple[int, int]]) -> list[int]:
    in_degree = [0] * num_nodes
    adjacency = [[] for _ in range(num_nodes)]

    for source, destination in edges:
        adjacency[source].append(destination)
        in_degree[destination] += 1

    queue = deque(node for node in range(num_nodes) if in_degree[node] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adjacency[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_nodes else []

Step through the course example:

In-degree array: [0, 1, 1, 2, 1]. Course 0 has no prerequisites. Course 3 has two.
Queue starts with [0].
Process 0: add to order, decrement neighbors 1 and 2, both reach 0, enqueue both.
Process 1: decrement neighbor 3 (now at in-degree 1, not ready yet).
Process 2: decrement neighbor 3 (hits 0), enqueue it.
Process 3, then 4.

Result: [0, 1, 2, 3, 4].

The cycle check is built in: if len(order) < num_nodes, some nodes got trapped in a cycle and never reached zero in-degree. You did not write a single extra line of cycle detection. It falls out of the algorithm naturally.

DFS: The One With Three Colors

The DFS approach explores fully before recording. A node gets pushed onto the result stack only after its entire subtree has been visited. Reading the stack in reverse gives you a valid topological order.

def topological_sort_dfs(num_nodes: int, edges: list[tuple[int, int]]) -> list[int]:
    adjacency = [[] for _ in range(num_nodes)]
    for source, destination in edges:
        adjacency[source].append(destination)

    state = [0] * num_nodes  # 0 = unvisited, 1 = in progress, 2 = done
    stack = []

    def dfs(node: int) -> bool:
        state[node] = 1
        for neighbor in adjacency[node]:
            if state[neighbor] == 1:
                return False  # cycle detected
            if state[neighbor] == 0:
                if not dfs(neighbor):
                    return False
        state[node] = 2
        stack.append(node)
        return True

    for node in range(num_nodes):
        if state[node] == 0:
            if not dfs(node):
                return []

    return stack[::-1]

The three-color state is the whole trick. 0 is unvisited. 1 is currently on the DFS stack, actively being explored. 2 is fully done.

If you encounter a node in state 1 during exploration, you found a back edge. That is a cycle. A node in state 2 is safe to skip. Its entire subtree is clean.

Why does a simple boolean visited array fail here? Because it cannot distinguish between "visited and done" (state 2, safe to skip) and "visited and currently on the stack" (state 1, cycle). The two situations look identical with one bit. A two-color approach will either miss real cycles or incorrectly flag nodes that were processed on a different DFS path. The three-color approach keeps them separate.

The Complexity Is Always O(V + E)

Both algorithms visit every vertex once and traverse every edge once. O(V + E) time, O(V + E) space for the adjacency list, plus O(V) for auxiliary structures: the queue or state array, the in-degree counts, the result list.

No complexity difference between the two approaches.

Kahn's makes the cycle check obvious and intuitive; the DFS version requires the three-color trick, which is harder to reconstruct under pressure. For most interviews, Kahn's wins on explainability. When an interviewer asks you to walk through your logic, "start with nodes that have no dependencies, work outward" is easier to narrate than "I maintain three visit states to distinguish back edges from cross edges."

Where This Pattern Shows Up

Topological sort appears directly in several well-known LeetCode problems:

Problem	What It Tests
LeetCode 207: Course Schedule	Detect a cycle in a prerequisite graph
LeetCode 210: Course Schedule II	Return the actual topological ordering
LeetCode 269: Alien Dictionary	Reconstruct ordering from word comparisons
LeetCode 310: Minimum Height Trees	Find root nodes via iterative leaf removal
LeetCode 1203: Sort Items by Groups	Two-level topological sort

207 and 210 are the most common. Solve both with Kahn's and DFS and you are covered for most appearances of this pattern.

The harder variants hide the graph. In 269 (Alien Dictionary), you construct the edge list by comparing adjacent words character by character before running topological sort on the implicit character ordering. The algorithm is identical. The setup is where candidates lose time, because the graph is never handed to you.

310 is particularly sneaky. The trick is running topological sort in reverse: repeatedly trim leaf nodes until one or two remain. Those are the roots of minimum-height trees. Recognizing "peel from the outside in" as reverse topological sort is what separates candidates who understand the algorithm from candidates who memorized a template. The template does not help when the problem runs backward.

Two Things That Trip Candidates Up

Forgetting cycle detection. Topological sort on a cyclic graph produces garbage output. Kahn's gives you the check free of charge (compare output length to node count). DFS requires the three-color state. A simple boolean visited array will not catch cycles involving nodes you have already finished on a different path. This is the most common failure mode on LeetCode 207, and it is the kind of failure that looks like it almost worked.

Assuming the ordering is unique. When a problem asks for "any valid ordering," Kahn's returns one based on queue insertion order. Test cases accept multiple correct answers. Do not add sorting logic unless the problem explicitly requires lexicographic or another specific order. It costs time and introduces bugs. Adding unnecessary constraints to an already-hard problem is a great way to introduce an edge case that breaks your solution on the last test case.

For the complete implementation reference including the DFS three-color proof, the topological sort deep dive covers both algorithms exhaustively.

The DP Connection Worth Knowing

One connection worth filing away: bottom-up dynamic programming is topological sort on the subproblem dependency DAG. The iteration order you choose when filling a DP table is implicitly a topological ordering of subproblems. Filling left to right, bottom to top, small to large, all of these choices are topological orderings. If an interviewer asks why you filled the table in that direction, you now have a real answer instead of "it felt right."

Topological sort uses BFS mechanics (Kahn's) or DFS mechanics (the stack approach). If either feels shaky, the BFS vs DFS breakdown is a useful prerequisite. For how to recognize graph structure from problem descriptions, see DFS pattern recognition.

Working through these problems out loud, getting feedback on whether your reasoning lands, is where real improvement happens. SpaceComplexity runs voice-based mock interviews that simulate the exact format where topological sort shows up, with rubric-based feedback on your explanation, not just your code.

Solve 207, then 210. Once with Kahn's and once with DFS. When both feel boring, you are ready.