L29 · Graphs III — Topological Sort

Series: LeetCode — From Basics to Interview-Ready · Session 29 / 65 · Phase 1 · Core patterns

Why this session exists

Two questions that look completely different turn out to be the same question: "in what order can I do these tasks" and "is there a circular dependency". Topological sort answers both with one pass, and the second answer falls out of the first for free.

That is the elegance worth internalising. You do not write a cycle detector and then a sorter. You write Kahn's algorithm, and if it emits fewer than n nodes, the leftovers are exactly the nodes trapped in cycles. One algorithm, two answers, no extra code.

The reason this appears so often in interviews is that dependency ordering is a real problem that real systems solve constantly — build systems, package managers, task schedulers, spreadsheet recalculation, database migrations. Course Schedule is a thin disguise over something the interviewer's team ships.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

indeg = [0] * n           — count incoming edges
q = deque(nodes with indeg == 0)
pop, emit, decrement neighbours, push the new zeros

Specifically: given n and prerequisites = [[a, b], ...] meaning you must take b before a, produce a valid ordering or an empty list if impossible.

What wobbles from memory: the edge direction. [a, b] with "take b before a" means the edge runs b → a, so indeg[a] increments, not indeg[b]. Getting that backwards produces a perfectly valid topological order of the reversed graph, which is wrong and looks right.

Pattern anatomy

The shape of problem that summons topological sort: a set of items plus constraints of the form "X must come before Y", and a question about ordering or feasibility. The graph must be directed. If the edges are undirected there is no notion of "before" and this pattern does not apply.

The invariant: at every step, the queue contains exactly the nodes whose dependencies have all been emitted already. A node's in-degree is the number of its prerequisites not yet satisfied. When that count hits zero, the node becomes legal to emit. That is the whole algorithm.

The template:

from collections import deque, defaultdict
 
def topo_sort(n, edges):
    """edges = [(u, v)] meaning u must come BEFORE v."""
    adj = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1                     # v gains an unsatisfied prerequisite
 
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in adj[node]:
            indeg[nxt] -= 1               # one prerequisite satisfied
            if indeg[nxt] == 0:
                q.append(nxt)             # push exactly when it hits zero
 
    return order if len(order) == n else []   # short order == cycle

Two lines carry all the meaning.

if indeg[nxt] == 0 — strictly equal, not less-than-or-equal. Testing <= 0 would push a node repeatedly if you ever double-decrement, and the equality test makes it structurally impossible to enqueue a node twice.

return order if len(order) == n else [] — this is the cycle detector. Nodes in a cycle mutually hold each other's in-degree above zero forever, so none of them ever enters the queue. If you emitted fewer than n, the missing ones form (or feed into) at least one cycle.

The DFS alternative, which produces a reverse post-order, is worth knowing but is not what I reach for:

def topo_dfs(n, adj):
    WHITE, GREY, BLACK = 0, 1, 2
    color = [WHITE] * n
    out = []
 
    def visit(u):
        if color[u] == GREY:
            return False                 # back edge -> cycle
        if color[u] == BLACK:
            return True
        color[u] = GREY
        for v in adj[u]:
            if not visit(v):
                return False
        color[u] = BLACK
        out.append(u)                    # append AFTER children: post-order
        return True
 
    for u in range(n):
        if not visit(u):
            return []
    return out[::-1]

Three colours, not two. GREY means "on the current recursion stack" and hitting a grey node is a back edge, which is a cycle. A two-state visited set cannot distinguish "already fully processed" from "currently being processed", and that distinction is the whole cycle test.

The cue

You are looking at a topological sort when the statement contains one of these tells:

1. "Prerequisites", "dependencies", "must come before", "requires". Course Schedule, Build Order, Task Scheduling. The phrasing is almost always literal.
2. "Is it possible to finish all / complete all" — a yes/no feasibility question over a dependency set. That is cycle detection, and Kahn answers it with the emitted-count check.
3. "Return any valid order" or "return the lexicographically smallest valid order". The second variant is the same algorithm with a min-heap instead of a deque.
4. Deriving an order from partial observations — Alien Dictionary. You are given evidence of pairwise precedence and asked to reconstruct a total order consistent with it.
5. A directed graph plus a question that is not about distance. If it were about distance you would be in session 28. Directed plus ordering equals topological.

The negative cue: an undirected graph never has a topological order. If the edges are symmetric, "before" is undefined. If you find yourself appending edges in both directions while writing a topological sort, you have misread the problem.

Guided solve

Course Schedule. numCourses courses labelled 0 to n−1, and prerequisites[i] = [a, b] meaning you must take course b before course a. Return whether you can finish all courses.

First, translate. "Must take b before a" means the dependency edge runs from b to a. So in my (u, v) convention where u comes before v, the pair [a, b] maps to u = b, v = a. Write this down before touching the keyboard, because reversing it silently is the single most common failure on this problem.

Second, restate the question. "Can you finish all courses" means "does a valid ordering exist", which means "is the dependency graph acyclic". So the answer is len(order) == numCourses.

from collections import deque, defaultdict
 
def canFinish(numCourses, prerequisites):
    adj = defaultdict(list)
    indeg = [0] * numCourses
    for course, prereq in prerequisites:      # take prereq BEFORE course
        adj[prereq].append(course)            # edge prereq -> course
        indeg[course] += 1
 
    q = deque(c for c in range(numCourses) if indeg[c] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
 
    return taken == numCourses

Note that I do not even build the order list here — the count is sufficient. When the follow-up asks for the actual schedule (Course Schedule II), swap taken += 1 for order.append(c) and return order if len(order) == numCourses else []. Same algorithm, two lines different. Say that out loud; it shows you see the family rather than two separate problems.

Trace on numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]. Edges: 0→1, 0→2, 1→3, 2→3. In-degrees: [0, 1, 1, 2]. Queue starts [0]. Pop 0, taken=1, decrement 1 and 2 to zero, push both. Pop 1, taken=2, decrement 3 to 1. Pop 2, taken=3, decrement 3 to 0, push. Pop 3, taken=4. Queue empty, taken == 4, return True.

Now break it. Add [0,3], making 3→0. In-degrees become [1, 1, 1, 2] and nothing starts at zero. Queue is empty immediately, taken = 0 < 4, return False. The cycle detection required no extra code at all.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• Course Schedule II — return the actual order, or an empty array if impossible. The change from Course Schedule is two lines; make sure you can state which two before you start typing.
• Alien Dictionary — given words sorted in an unknown alphabet, derive the letter order. Two things to think about before coding: how do you extract a precedence edge from a pair of adjacent words, and what is the invalid case where one word is a prefix of an earlier word.

If both land early, do Minimum Height Trees. It is a topological-style peeling of leaves in an undirected tree — a good stress test of whether you understand why in-degree peeling works, since the direction argument does not apply and you peel degree-1 nodes instead.

Common failure modes

Reversing the edge direction. [a, b] with "b before a" is the edge b→a. Building a→b gives a valid topological order of the wrong graph. No crash, plausible-looking output, wrong answer. Write the direction on paper first.

Incrementing the wrong in-degree. indeg[v] += 1 where v is the dependent, not the prerequisite. The prerequisite is the source and its in-degree is untouched by this edge.

Testing indeg[nxt] <= 0 instead of == 0. With a correct implementation both behave identically, but the equality form makes double-enqueueing structurally impossible, which matters when the input contains duplicate edges.

Using a two-state visited set for DFS cycle detection. You need three states. visited alone cannot tell "finished" from "in progress", so it reports a cycle on any diamond-shaped DAG — a node reachable by two different paths.

Forgetting the prefix case in Alien Dictionary. If ["abc", "ab"] appears in that order, no alphabet is consistent, because a prefix must sort first. There is no edge to extract, so a naive implementation returns a valid-looking order for an impossible input.

Not handling isolated nodes. A course with no prerequisites and no dependents has in-degree zero and belongs in the initial queue. Building the queue by iterating over the edge list rather than range(n) silently drops them, and the count check then reports a false cycle.

Complexity

Time: O(V + E). Building the adjacency list and in-degree array is one pass over the edges, O(E). Seeding the queue scans all nodes, O(V). In the main loop each node is dequeued exactly once, and dequeuing a node walks its adjacency list once, so across the whole run every edge is traversed exactly once. Total O(V + E).

The lexicographic variant with a heap is O(V log V + E) — the log factor comes from up to V pushes and V pops on the heap.

Space: O(V + E). The adjacency list is O(V + E), the in-degree array is O(V), and the queue holds at most V entries. For the DFS form, the recursion stack adds O(V) in the worst case, which is a chain graph.

For Alien Dictionary specifically, V is bounded by 26 and E by the number of adjacent word pairs, so the graph work is trivial. The real cost is the O(total characters) scan to extract the edges.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Course Schedule enters the queue today. If you had to run the sample input to work out which way the edge pointed, log it hint at best — the direction should come from reading the sentence, not from experiment.