Pattern 20 of 22
Topological Sort Pattern: Template + 32 LeetCode Problems
Order a set of tasks so that every dependency comes before the thing that needs it.
- Easy
- 0
- Medium
- 14
- Hard
- 18
- Time
- O(V + E)
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 cycleComplexity 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.
Eyes only
Meet the topological sort problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
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 LeetCode topics
Medium (14)
| No. | Problem | Topics |
|---|---|---|
| 0207 | Course Schedule | |
| 0210 | Course Schedule II | |
| 0310 | Minimum Height Trees | |
| 0444 | Sequence ReconstructionPremium | |
| 0802 | Find Eventual Safe States | |
| 0851 | Loud and Rich | |
| 1059 | All Paths from Source Lead to DestinationPremium | |
| 1136 | Parallel CoursesPremium | |
| 1245 | Tree DiameterPremium | |
| 1462 | Course Schedule IV | |
| 1786 | Number of Restricted Paths From First to Last Node | |
| 1976 | Number of Ways to Arrive at Destination | |
| 2115 | Find All Possible Recipes from Given Supplies | |
| 2192 | All Ancestors of a Node in a Directed Acyclic Graph |
Hard (18)
Topological Sort pattern FAQ
What is the topological sort pattern?
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.
How many LeetCode problems use the topological sort pattern?
This page lists 32 LeetCode problems that the topological sort pattern applies to: 0 Easy, 14 Medium and 18 Hard. 24 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the topological sort pattern?
O(V + E) time and O(V + E) space. 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.
When should I use the topological sort pattern in an interview?
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.
Which topological sort problem should I start with?
LeetCode 207. Course Schedule is the lowest-numbered Medium problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to topological sort?
Breadth-First Search, Depth-First Search, Union-Find, Greedy. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.