Topological Sort Pattern: Template + 32 LeetCode Problems

What the topological sort pattern is

A topological sort linearises a directed acyclic graph so that every edge points forward: if u must happen before v, u appears earlier in the output. Kahn's algorithm computes it by counting incoming edges, starting from every node with an indegree of zero, and decrementing the indegree of each neighbour as a node is emitted — a neighbour joins the frontier the moment its last prerequisite is gone. The cycle check is free and is often the real question: if the output is shorter than the node count, the nodes that never reached indegree zero are exactly the ones trapped in a cycle. The DFS variant reaches the same answer by appending each node after its descendants finish and reversing the result, which is more natural when you are already recursing, but Kahn's is easier to reason about under interview pressure because its state is just an array of counters and a queue.

When to use it

• —The problem describes prerequisites, dependencies, build order, or a course schedule.
• —You need to know whether a directed graph has a cycle, and which nodes are in it.
• —An ordering is requested and the constraints are all of the form "a before b".
• —A DAG's nodes must be processed in an order where each node's inputs are already computed — dynamic programming over a graph.

The topological sort template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 32 problems listed below.

from collections import deque

def topological_order(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for before, after in edges:       # edge before -> after
        graph[before].append(after)
        indegree[after] += 1

    queue = deque(node for node in range(n) if indegree[node] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:   # last prerequisite just cleared
                queue.append(neighbour)

    return order if len(order) == n else []   # a short order means a cycle

Complexity characteristics

Time

O(V + E)

Auxiliary space

O(V + E)

Kahn's algorithm touches every node once, when it leaves the queue, and every edge once, when its target's indegree is decremented — so the cost is linear in the size of the graph. The space is the adjacency lists plus the indegree array plus the queue. The DFS variant has the same time bound and trades the queue for a recursion stack that can reach depth V.

All 32 topological sort LeetCode problems

Every problem in the library the topological sort pattern applies to, grouped by LeetCode's own difficulty rating. 24 of the 32 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Topological Sort pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.