Topological Sort ·

Introduction
#

Topological sort is used on directed dependency graphs. It answers questions like:

Can all tasks be completed?
What is one valid dependency order?
Which nodes become available after their prerequisites are satisfied?
How can information be propagated through a DAG?

The core interview skill is choosing the correct graph direction and explaining what the in-degree means.

Core Idea
#

Kahn’s algorithm keeps all nodes whose prerequisites are already satisfied:

queue = all nodes with indegree 0

When a node is processed, it unlocks its outgoing neighbors:

for nei in graph[node]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

If all nodes are processed, the graph has no cycle. If some nodes remain blocked, a cycle or impossible dependency exists.

Template
#

from collections import deque
from typing import List

def topo_order(n: int, edges: List[List[int]]) -> List[int]:
    graph = [[] for _ in range(n)]
    indeg = [0] * n

    for pre, node in edges:
        graph[pre].append(node)
        indeg[node] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []

    while q:
        node = q.popleft()
        order.append(node)
        for nei in graph[node]:
            indeg[nei] -= 1
            if indeg[nei] == 0:
                q.append(nei)

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

Variants
#

Cycle Detection
#

For LC 207, the return value is boolean:

processed_count == numCourses

Return An Ordering
#

For LC 210, the popped queue order is the topological order. Return an empty list if a cycle remains.

Dependency Unlocking
#

For recipes and supplies, the queue starts from already available items, not just graph nodes with zero in-degree.

Reverse Outdegree Trimming
#

For eventual safe states, safe nodes are proven backward from terminal nodes. Track remaining outdegree, not indegree.

Two-Level Topological Sort
#

For grouped items, sort both item dependencies and group dependencies, then emit item buckets in group order.

Two Independent Orders
#

In LC 2392 the row and column conditions do not affect each other, so run one topological sort for each: number x goes in row row_pos[x] and column col_pos[x]. A cycle on either side means an empty matrix.

All Paths Lead to Destination
#

LC 1059 is reverse outdegree trimming too: working back from the destination, a node is safe only when all its outgoing edges lead to safe nodes; the answer is whether the source is safe. Check the destination first: any outgoing edge (including a self-loop) means infinitely many paths.

Common Mistakes
#

Reversing edge direction and making the in-degree meaningless.
Returning a partial order when a cycle remains.
Treating an undirected graph as a topological sort problem.
Calling an outdegree counter in_degree in reverse-trimming problems.
Forgetting that propagation problems need state meaning, not just ordering.
In my DFS version I did not check whether the destination has outgoing edges, so a self-loop like [[0, 0]] counted as success (LC 1059).