Problem Statement

Topological Sort

You are given a set of tasks, drawn as a graph. The graph is "directed," which means each connection points one way, like an arrow. An arrow from task u to task v means "u must come before v." The graph is also a "DAG," short for directed acyclic graph, which just means the arrows never loop back on themselves, so there is no impossible situation where A waits on B and B waits on A. Your job is to put all n tasks in an order so that every task comes before the tasks that depend on it. That ordering is called a "topological order." Think of it like getting dressed: socks before shoes, shirt before jacket. Any order that respects all the rules is a valid answer.

mediumGraphGraphsTime: O(V+E) · Space: O(V+E)

Signals to notice

order elements respecting dependenciesno element before its prerequisitesDAG linearization

Brute force first

Try all permutations and check validity. Brute-force ordering. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Kahn's algorithm (BFS): compute in-degrees, start with in-degree-0 nodes, process and decrement neighbors' in-degrees. Or DFS with post-order reversal. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `n=4, edges=[[1,0],[2,0],[3,1],[3,2]]`

Build: graph{1:[0],2:[0],3:[1,2]}, in_degree=[2,1,1,0]
Seed queue with in_degree-0 nodes: queue=[3], result=[]
Pop 3 -> result=[3]; dec nbrs 1,2 -> in_degree=[2,0,0,0]; enqueue 1,2 -> queue=[1,2]
Pop 1 -> result=[3,1]; dec nbr 0 -> in_degree[0]=1 (not 0, skip); queue=[2]
Pop 2 -> result=[3,1,2]; dec nbr 0 -> in_degree[0]=0; enqueue 0 -> queue=[0]
Pop 0 -> result=[3,1,2,0]; no neighbors; queue=[] empty
len(result)=4 == n -> return [3,1,2,0]

What must stay true

In a topological order, every edge (u,v) means u appears before v. Nodes with in-degree 0 have no unmet prerequisites and can be processed first. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

build adjacency list + in_degree from edges
queue <- all nodes with in_degree == 0
while queue not empty:
    node <- queue.pop_front(); result.append(node)
    for nei in graph[node]:
        if --in_degree[nei] == 0: queue.push(nei)
return result if len(result) == n else []   # else: cycle

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Confusing topological sort with regular sorting — topological sort works on DAGs (no cycles). If the graph has a cycle, no valid topological order exists. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Graphs Pattern