Topological sort

What it is

Topological sort produces a linear ordering of the nodes of a directed graph such that every edge points from an earlier node to a later one — a valid answer to "what order can these dependent things happen in." It only exists when the graph has no cycle, so the algorithm and the cycle check are the same piece of work: repeatedly take a node with no remaining unsatisfied dependency (in-degree zero), output it, and remove its outgoing edges, which may free up new nodes to take next (Kahn's algorithm); if you run out of removable nodes before every node is output, a cycle exists and no ordering is possible.

When it applies

• Items have explicit pairwise "A before B" constraints (prerequisites, build steps, scheduling dependencies) and you need one valid full ordering, or just need to know whether one exists.
• You're inferring an ordering relationship indirectly from data — comparing adjacent sorted strings to deduce which letter precedes which — rather than being handed the edges directly.
• The graph is a tree and you need to reason about layers from the outside in (repeatedly stripping the current leaves is the same in-degree-zero mechanism, even without calling it "prerequisites").
• Needing only whether the graph is connected, or the shortest path between two nodes, with no ordering constraint at all, is bfs/dfs territory instead — topological sort specifically answers "in what order," not "how far" or "is it reachable."

Tells in the problem

• "Must be completed before," "must come before," or "prerequisite," paired with a request for a valid order or a yes/no on whether one exists.
• "Return an empty list / false if the constraints are circular" — an explicit cycle-detection requirement bundled with the ordering.
• An ordering must be inferred from indirect evidence (already-sorted words, adjacent comparisons) rather than given as an explicit edge list.
• A tree problem framed around "peel away the outermost layer repeatedly" — structurally the same in-degree-zero removal, even without the word "prerequisite" anywhere.
• Constraints given as ordered pairs [a, b] meaning one must precede the other, especially with a note that pairs are not repeated (a simple DAG-or-not check).

The classic mistake

Building the ordering (usually via DFS with a visited set) but forgetting to distinguish "currently being visited on this recursion path" from "already fully processed" is the error interviewers report most — without that distinction, a back edge to a node that's still mid-recursion looks identical to a normal cross edge to an already-finished node, so a genuine cycle slips through undetected. This happens because a single "visited" boolean is enough to avoid infinite recursion, so it's easy to stop there and think cycle detection is already handled. Catch it by using two states (in-progress, done) instead of one, or by using Kahn's algorithm instead, where the cycle check falls out for free as "fewer nodes were output than exist."

Questions to start with

• Course Schedule — the pure yes/no cycle-detection question, the smallest version of this pattern.
• Course Schedule II — the same graph, but now the actual ordering is the answer, not just whether one exists.
• Minimum Height Trees — the same in-degree-zero peeling mechanism applied to an undirected tree instead of a dependency graph.
• Alien Dictionary — the edges themselves must be inferred from adjacent word comparisons before any sorting can begin.