Topological Sort Pattern: Ordering Tasks With Dependencies

TL;DR: When items have "this must come before that" rules, model them as a directed graph and produce an order in which every rule points forward. Kahn's algorithm does it with a queue and a count of incoming edges per node, in O(V + E). The part candidates undervalue is that the same single pass also detects impossibility: if you finish having emitted fewer nodes than you started with, the rules contain a cycle. One template answers both "give me a valid order" and "is a valid order possible", which is why this pattern shows up in interviews as two questions that look different and are not.

This is the eleventh deep dive in our pattern series (the full map lives in the hub), following backtracking. Topological sort is the most operational pattern in the series: build systems, task schedulers, package managers, and spreadsheet recalculation all run on it. Interviewers like it because the setup is easy to state in product language and the implementation exposes whether you can translate a description into a graph correctly, which is a skill that transfers directly to real work.

The tell: how to recognize a topological sort problem

Suspect this pattern when the question contains ordering constraints between items:

• "prerequisites", "dependencies", "build order"
• "task B cannot start until task A finishes"
• "can you finish all the courses" (this is cycle detection wearing a schedule)
• "return an order such that every rule is satisfied"
• "detect a cycle in a directed graph"
• "derive the alphabet order" from a sorted list of words
• "minimum number of semesters" or rounds to finish everything

The unifying shape: a set of items plus pairwise "before" rules, and a question about arranging them or about whether arranging them is possible at all. Two words are worth memorizing as triggers, prerequisite and dependency, because they almost never appear in problems that need something else.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: a task can run as soon as nothing is still waiting to come before it.

Translate "nothing is still waiting" into a number and you get in-degree, the count of edges pointing into a node. A node with in-degree 0 has no unmet prerequisites, so it is safe to run now. Running it removes its outgoing edges, which lowers the in-degree of its dependents, which may release the next batch. Repeat until nothing is releasable.

The second half of the insight is what makes the algorithm complete: if you stop with nodes left over, every one of them is still waiting on something, which can only happen if they are waiting on each other. That is a cycle. You do not need a separate cycle-detection pass, because the failure to finish is the detection. Say that in an interview and you have covered both questions the problem could ask.

The template

Kahn's algorithm is the interview default because it is short and it narrates well:

from collections import deque

def topological_order(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for before, after in edges:          # "before" must come before "after"
        graph[before].append(after)
        indegree[after] += 1             # the dependent gains a prerequisite

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

    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1           # one prerequisite satisfied
            if indegree[nxt] == 0:
                queue.append(nxt)

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

The last line carries the cycle detection. For a question phrased as "can you finish all courses", return len(order) == n instead of the list, and nothing else changes.

The edge direction rule deserves its own sentence, because reversing it is the most common bug in this pattern. If the input says "to take course a you must first take course b", then b comes before a, so the edge runs b -> a and you increment indegree[a]. LeetCode's Course Schedule gives pairs as [course, prerequisite], which is the reverse of the order you need, so read the problem statement carefully and write the direction down before coding. A solution with flipped edges still runs, still terminates, and returns a plausible wrong order, which is the worst kind of bug to find under time pressure.

The variant that answers "how long", not just "what order"

Some questions ask for the minimum number of rounds rather than a sequence: minimum semesters to finish all courses, or the number of steps to complete a build. Process the queue one full level at a time and count levels:

    levels = 0
    while queue:
        for _ in range(len(queue)):      # everything currently releasable
            node = queue.popleft()
            processed += 1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)
        levels += 1

This is the same structure as level order traversal in a tree, applied to a graph. Everything in one level has no dependency on anything else in that level, so it can all run in parallel, which is exactly what "one semester" or "one build stage" means.

The compass: Kahn's algorithm or DFS?

Both produce valid topological orders, and interviewers sometimes ask you to compare them.

• Kahn's algorithm (BFS with in-degrees) is the better default. Cycle detection is a length check, the level variant is nearly free, and the narration matches how people describe dependency resolution out loud.
• DFS produces an order by appending nodes after exploring all their descendants and then reversing the result. Cycle detection needs three node states (unvisited, in progress, finished), where finding an in-progress node means a cycle. It is elegant, and it is the right choice when you already need DFS for another reason.

Choose Kahn's unless something in the problem pushes you toward DFS, and be ready to say why in one sentence.

Want the whole family taught in order? The topological sort chapter of Grokking the Coding Interview builds from Course Schedule through Alien Dictionary with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Course Schedule: the cycle question. Return whether the emitted count equals the node count.
• Course Schedule II: the same code returning the order. These two being one problem is the point.
• Minimum Height Trees: the undirected relative. Repeatedly remove leaves (degree 1) until one or two nodes remain. Same peeling idea, different degree rule.
• Parallel Courses: the level counting variant, asking for minimum semesters.
• Sequence Reconstruction: is the valid order unique? It is unique exactly when the queue never holds more than one node at a time, because a choice means more than one valid order exists.
• Alien Dictionary: the hard one, and the difficulty is entirely in building the graph. Compare adjacent words character by character, and the first position where they differ gives one edge. Only one edge per word pair. There is also an invalidity case that catches most candidates: if a word is followed by a strict prefix of itself, such as ["abc", "ab"], the input is impossible and you must return early.

The three mistakes that sink candidates

1. Reversed edge direction. Increment the in-degree of the dependent, not the prerequisite. Write down which element of each input pair is "before" before you write the loop, especially since Course Schedule hands you the pairs backwards.

2. Skipping the cycle check. Returning order without comparing its length to n gives a partial ordering on cyclic input and looks correct on the sample cases. The check is one comparison, so always write it.

3. Building the graph wrong in Alien Dictionary. Taking an edge from every differing character instead of only the first one produces constraints the input never stated, and missing the prefix case returns an order for an impossible input. In graph problems generally, the modeling is graded more heavily than the traversal.

Practice ladder

In order, each rung adding one wrinkle.

1. Find the Town Judge (E): warm up on in-degree and out-degree counting.
2. Course Schedule (M): cycle detection through a length check.
3. Course Schedule II (M): the same pass returning the order.
4. Minimum Height Trees (M): peeling leaves in an undirected graph.
5. Parallel Courses (M): the level counting variant.
6. Sequence Reconstruction (M): uniqueness through queue size.
7. Alien Dictionary (H): graph construction is the problem.
8. Stretch: Course Schedule IV (M), reachability queries on top of the ordering.

Then write the tell in your own words ("I should suspect topological sort when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One insight (a task is ready when nothing is waiting to come before it), one counter (in-degree), one loop (release, emit, decrement, release again), and one line that turns the algorithm into a cycle detector (compare the emitted count with the node count). Add the level variant and you also answer "how many rounds". The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Union-Find, the tool for connected components when edges arrive over time.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential graph problems in its 6-week plan.

FAQs

What is a topological sort in simple terms? An arrangement of items that respects every "must come before" rule, so that each item appears after everything it depends on. It exists only for directed graphs with no cycles, because a cycle would require an item to come before itself.

How does Kahn's algorithm detect a cycle? By counting. Every node that gets emitted had all its prerequisites satisfied. If the loop ends having emitted fewer nodes than the graph contains, the remaining nodes all still have unmet prerequisites, which is only possible if they depend on each other. So a short result is proof of a cycle.

Which direction should the edges point? From the prerequisite to the dependent. If b must be done before a, add the edge b -> a and increment the in-degree of a. Note that Course Schedule supplies pairs as [course, prerequisite], which is the reverse of that, so read the input format carefully.

Should I use BFS or DFS for topological sort? BFS with in-degrees (Kahn's algorithm) is the better interview default, because cycle detection is a length check and the level-by-level variant answers "minimum rounds" for free. DFS works too, using post-order plus three node states to catch cycles, and it fits when you already need DFS for another part of the problem.

Is topological sort asked at FAANG companies? Yes. Course Schedule and Course Schedule II are among the most frequently asked graph questions anywhere, Alien Dictionary is a recurring hard at Google and Meta, and the dependency framing appears often in infrastructure-oriented teams because it mirrors real build and scheduling systems.