Topological Sort — the shape behind dozens of interview problems.

Topological Sort in Python

from collections import deque, defaultdict
def topo_sort(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    indeg = [0] * n
    adj: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    out: list[int] = []
    while q:
        u = q.popleft()
        out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return out if len(out) == n else None

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the topological sort pattern?

Topological Sort is linear ordering of a dag consistent with its dependencies. Time O(V + E); space O(V).

When should I use topological sort?

Use it when: Schedule tasks with prerequisite edges. Detect cycles in a directed graph. Any "must-happen-before" constraint.

What are the most common topological sort bugs?

Not handling cycles — return None rather than partial order. Using DFS-based topo without a "color" state → miss cycle detection. Forgetting to decrement indegree exactly once per edge.

What problems use the topological sort pattern?

Representative scenarios: Build-Order Planner — order tasks with dependencies. Dialect Sorter — derive letter order from a sorted alien dictionary. Certification Track — sequence courses by prereqs.

Is topological sort on the Blind 75?

Yes — Topological Sort is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.