Topological Sort

At a glance

The instinct

Whenever a problem says "before", "depends on", "prerequisite" or "must be built after", draw an arrow from the thing that must happen first to the thing that waits for it. You now have a directed graph. A valid schedule exists exactly when that graph has no cycle, and the schedule itself is a topological order.

The most interview-friendly way to compute it is Kahn's algorithm: count incoming arrows (in-degree) for every node, start with the nodes that have zero, and every time you "finish" a node, decrement its followers. Followers that reach zero join the queue. If you finish fewer than n nodes, the leftovers are trapped in a cycle.

Recognise it

Not this pattern if...

• The graph is undirected and you only need connectivity: DFS/BFS or Union-Find.
• You need the shortest path by edge count without ordering constraints: BFS.
• Edges are "a equals b" relations rather than "a before b": Union-Find.
• The order is fully given and you only sort by a key: just sort.

Memory hack

Analogy: getting dressed. Socks before shoes, underwear before trousers, trousers before belt. You start with anything that has no "before" (socks, underwear, shirt), and each item you put on unlocks the next. Trying to wear shoes before socks is a cycle you cannot satisfy.

Say it out loud in the interview:

1. "Edge from prerequisite to dependent; I'll build adjacency lists and in-degrees."
2. "Queue every zero in-degree node; pop, append to order, decrement neighbours, enqueue new zeros."
3. "If the order has fewer than n nodes, there is a cycle, so the answer is impossible."

How it works

flowchart TD
  A["Build adjacency list and in-degree per node"] --> B["Enqueue all nodes with in-degree 0"]
  B --> C{"Queue empty?"}
  C -- no --> D["Pop u, append u to order"]
  D --> E["For each edge u to v: indegree of v minus 1"]
  E --> F{"indegree of v is 0?"}
  F -- yes --> G["Enqueue v"]
  F -- no --> C
  G --> C
  C -- yes --> H{"order size equals n?"}
  H -- yes --> I["Valid topological order"]
  H -- no --> J["Cycle: no valid order"]

DFS alternative. Colour nodes white (unvisited), grey (on the current path) and black (done). Reaching a grey node means a back edge, which is a cycle. Appending each node when it turns black produces a reverse topological order. This three-colour DFS is also the cleanest way to solve Find Eventual Safe States: a node is safe if its DFS finishes black without ever touching grey.

Building edges from comparisons (Alien Dictionary). Compare each pair of adjacent words and find the first differing letter; that gives one edge. If no letter differs and the first word is longer (like "abc" before "ab"), the input is invalid.

Java template

import java.util.*;

class TopoSort {
    // Kahn's algorithm. edges[i] = {before, after}. Returns empty array if a cycle exists.
    static int[] order(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }

        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);

        int[] out = new int[n];
        int idx = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            out[idx++] = u;                      // problem-specific: track layer, time, etc.
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
        }
        return idx == n ? out : new int[0];
    }

    // Three-colour DFS: returns false on a cycle; post-order fills 'post' in reverse topo order.
    static boolean dfs(int u, List<List<Integer>> adj, int[] state, List<Integer> post) {
        state[u] = 1;                            // 1 = grey, on current path
        for (int v : adj.get(u)) {
            if (state[v] == 1) return false;     // back edge: cycle
            if (state[v] == 0 && !dfs(v, adj, state, post)) return false;
        }
        state[u] = 2;                            // 2 = black, fully explored
        post.add(u);
        return true;
    }
}

Course Schedule gives pairs as [course, prereq], so the edge is prereq → course; flip the indices accordingly.

Complexity

Variations

• Feasibility only: count processed nodes. Example: Course Schedule.
• Produce the order: return the queue's output. Example: Course Schedule II.
• Infer edges first: derive constraints from adjacent items. Example: Alien Dictionary.
• Reverse-graph peeling / colouring: find nodes not on or leading to a cycle. Example: Find Eventual Safe States.
• Leaf trimming on undirected trees: peel degree-1 nodes until 1-2 remain. Example: Minimum Height Trees.
• Layered / two-level sort: count rounds, or sort groups then items within groups. Example: Sort Items by Groups Respecting Dependencies.
• Lexicographically smallest order: replace the queue with a min-heap.

Common mistakes

• Forgetting the cycle check (processed == n) and returning a partial order as if it were complete.
• Using a plain visited boolean in DFS cycle detection; it cannot tell a back edge (cycle) from a cross edge to a finished node. Use three states.
• Storing Alien Dictionary edges in a Set but incrementing in-degree on every comparison; duplicates then never drain to zero. Increment only when set.add returns true.
• Missing nodes that appear in no edge: they still have in-degree 0 and must be in the output.
• In Alien Dictionary, ignoring the invalid "longer word is a prefix-earlier" case.

All practice problems

6 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.