Topological Sort

1The mental model (what this really is)#

Topological sort answers one plain question: given tasks where some must happen before others, what order can I do them in?

• Think about courses. You cannot take Algorithms before Intro to Programming, so Intro comes first.
• Some courses have no relationship at all, so their order does not matter.
• A topological sort is any ordering that respects every "X before Y" rule, and nothing more.

The structure underneath is a directed graph.

• Each node is a task. An edge from A to B means "A must come before B."
• The whole thing only makes sense if the graph is a DAG, a Directed Acyclic Graph.
• Acyclic is the keyword. If A depends on B and B depends on A, no valid order exists: each waits on the other forever. That is a cycle.
• In practice the sort itself is the easy part. The points live in the cycle check and in getting edge direction right.

Burn this into memory: there is usually more than one correct answer.

• If three tasks have no dependencies between them, any of the 6 orderings of those three is fine.
• So "return a valid ordering" is not asking for a unique answer. Do not waste time hunting for one.
• If they want a specific one (smallest lexicographic order), that is a variation, handled in section 5.

2How to recognize it (the signals in a problem)#

You should feel the pull toward topological sort the moment you see these words:

• "prerequisites," "dependencies," "before," "after," "must come first"
• "ordering" or "sequence" where the order is constrained by rules
• "Can you finish all tasks?" or "Is there a valid schedule?" (this is really "is the graph acyclic?")
• Build systems, task schedulers, course schedules, package installs, recipe steps
• Any input that hands you pairs like [a, b] meaning a one-way relationship between two items

The tell that separates this from a plain graph traversal:

• The problem cares about an order that respects direction.
• Not "can I reach this node," but "what must I finish before I am allowed to start this one."

When it does NOT apply:

• Mutual relationships (friendship, two-way roads) are an undirected graph, and topological sort does not fit.
• "Ordering" means nothing without direction. Edges must point one way and carry a meaning of precedence.
• If you cannot say which of two related items comes first, this is not your pattern.

3The template (how it works, with pseudocode)#

Two standard approaches exist. Learn Kahn's algorithm (BFS with in-degrees) first.

• It is the one I reach for in interviews: it detects cycles for free and the logic is hard to get wrong under pressure.
• The DFS version needs a separate three-state marking just to catch cycles, and that extra bookkeeping is where people slip.

The idea behind Kahn's:

• A node with zero incoming edges has no unmet prerequisites, so it is safe to do now.
• Do it, remove its outgoing edges, and that may drop another node to zero and free it.
• Repeat until nothing is left.

function topo_sort(num_nodes, edges):
    # Build adjacency list and in-degree count
    graph = [[] for _ in range(num_nodes)]
    in_degree = [0] * num_nodes
    for (a, b) in edges:          # a must come before b
        graph[a].append(b)
        in_degree[b] += 1

    # Start with every node that has no prerequisites
    queue = [n for n in range(num_nodes) if in_degree[n] == 0]
    order = []

    while queue is not empty:
        node = queue.pop_front()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1   # we "consumed" one prerequisite
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If we couldn't place every node, there's a cycle
    if len(order) == num_nodes:
        return order
    else:
        return []     # or raise "cycle detected"

That last check is the whole game.

• If a cycle exists, the nodes inside it never hit in-degree zero, so they never enter the queue, and order comes up short.
• One comparison, len(order) == num_nodes, tells you the graph is invalid.
• Do not skip it, and say out loud why it works: cyclic nodes cannot fit.

The DFS version is worth knowing so you can name it:

• Run a depth-first search, and after you finish exploring all descendants of a node, push it onto a stack. Reverse the stack at the end for your order.
• Cycle detection needs a three-color marking (unvisited, in-progress, done). Reach an in-progress node and you have looped back on yourself, which is a cycle.
• It works, but under stress the in-progress tracking trips people up, and a missing color check silently returns a wrong order. I default to Kahn's.

4A worked example (walk through one problem step by step, in your own words)#

The classic: Course Schedule II.

• You have numCourses courses labeled 0 to n minus 1, plus a list of prerequisite pairs.
• Each pair [a, b] means you must take course b before course a.
• Return any valid order to take all courses, or an empty list if it is impossible.

Let's use numCourses = 4 and prerequisites = [[1,0], [2,0], [3,1], [3,2]].

First, read the edges carefully, because this is exactly where points leak.

• The pair [1,0] means "take 0 before 1," so the edge goes from 0 to 1.
• The arrow points from the prerequisite to the course that needs it.
• Translate all four, slowly: [1,0] gives 0 to 1, [2,0] gives 0 to 2, [3,1] gives 1 to 3, [3,2] gives 2 to 3.

Now build in-degrees (how many prerequisites each course has):

• Course 0: nobody points to it. In-degree 0.
• Course 1: course 0 points to it. In-degree 1.
• Course 2: course 0 points to it. In-degree 1.
• Course 3: courses 1 and 2 point to it. In-degree 2.

Here's the shape of the graph:

Now trace it.

• Start the queue with everything at in-degree 0. That is just [0].
• Process 0. order = [0]. Neighbors are 1 and 2. Drop each one's in-degree by one. Course 1 goes 1 to 0, free, push it. Course 2 goes 1 to 0, free, push it. Queue is now [1, 2].
• Process 1. order = [0, 1]. The only neighbor of 1 is 3. Course 3 drops from 2 to 1. Not zero, so it waits. Do not push 3 yet. Queue is [2].
• Process 2. order = [0, 1, 2]. Neighbor of 2 is 3. Course 3 drops from 1 to 0. Now truly free, push it. Queue is [3].
• Process 3. order = [0, 1, 2, 3]. No neighbors. Queue is empty.

The result:

• We placed all 4 courses, so len(order) == 4 == numCourses and the answer is [0, 1, 2, 3].
• Note that [0, 2, 1, 3] would have been equally correct if the queue had handed us 2 before 1.
• Both respect every rule. That is the "more than one answer" point from section 1, made concrete.

Now break it on purpose.

• Add the pair [0,3], meaning take 3 before 0, edge 3 to 0.
• That creates a loop: 0 needs 3, and 3 needs 1 and 2, which need 0.
• Every course in that tangle now has in-degree at least 1, so the initial queue is empty, nothing gets processed, order stays empty, and len(order) = 0 != 4.
• We return []. Impossible schedule, correctly caught. That is the exact moment the cycle check earns its keep.

5Variations and gotchas#

Just checking feasibility.

• Some problems ("Course Schedule I") only ask "can you finish all tasks?" You return a boolean, not the order.
• Run Kahn's and return whether you placed every node (len(order) == num_nodes).
• Same algorithm, simpler return.

Lexicographically smallest order.

• When the problem wants a specific tie-break (smallest number first, alphabetical), swap the plain queue for a min-heap.
• Instead of processing zero in-degree nodes in arbitrary order, always pop the smallest available one.
• That single swap handles it, and it costs you a log factor (see section 6).

Alien Dictionary style.

• You are given words sorted in some unknown alphabet and must recover the letter order.
• Turn it into a graph first: compare each pair of adjacent words, find the first differing character, and that one difference gives you a single ordering edge.
• Then topological sort the letters. The hard part is building the graph, not the sort.
• Watch the edge case where a longer word comes before its own prefix (like "abc" before "ab"), which is invalid input and should return "" rather than a bogus order.

Counting all orderings.

• Rare in interviews. If asked how many valid orderings exist, that is a harder combinatorial problem, not a simple topo sort.
• Name it as such and do not pretend one Kahn's pass answers it.

The disconnected graph trap.

• Your graph may have several separate pieces, or isolated nodes with no edges at all.
• An isolated node has in-degree 0, so it belongs in the initial queue.
• Start BFS from only one node and you silently drop every other component.
• Initialize the queue by scanning all nodes for in-degree zero, not just the first one you find.

6Complexity#

Time: O(V + E).

• V is the number of nodes, E the number of edges. You touch each node once and each edge once.
• That is optimal: you cannot order the graph without at least looking at every node and every dependency.

Space: O(V + E).

• The adjacency list holds all E edges, and the in-degree array plus the queue hold up to V entries.

The lexicographic variation: O(V log V + E).

• Each of the V heap operations is logarithmic.
• Still fast, just slightly more than linear, and worth stating explicitly if you reach for the heap.

7Mistakes that cost people the round#

Reversing the edge direction.

• This is the number one killer.
• When a pair means "b before a," decide once, out loud, which way the arrow points, and write it on the board before you touch code.
• Get this backward and your entire sort is inverted, often unnoticed until the sample test fails and your time is gone.

Forgetting cycle detection.

• Candidates return order without checking its length against the node count.
• If the graph has a cycle, you hand back a partial, wrong answer and claim it is valid.
• Always verify len(order) == num_nodes, and narrate why: "if there is a cycle, those nodes never reach in-degree zero, so they will not fit, and the length tells me."

Only seeding the queue with one node.

• Disconnected components and isolated nodes break naive solutions.
• Scan all nodes for in-degree zero at the start, every time.

Mutating in-degree wrong.

• Decrement the neighbor's in-degree, and only push it when it hits exactly zero.
• Push it the moment you touch it, before it is truly free, and you produce garbage orderings that violate a prerequisite you have not satisfied yet.
• One off-by-one here and you are done.

Not clarifying uniqueness.

• Confirm early whether any valid order is acceptable or they want a specific one (smallest, alphabetical).
• Thirty seconds of asking saves you from solving the wrong problem and from a heap you did not need.

Treating an undirected graph as topo-sortable.

• If edges have no direction or precedence meaning, this pattern does not fit.
• Make sure the dependency is actually one-way before you start building in-degrees.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one adds exactly one layer on the last.

Warm-up and core:

• Course Schedule (feasibility only, learn the cycle check in isolation)
• Course Schedule II (return the order, the canonical problem, the one from section 4)
• Find Eventual Safe States (cycle reasoning, reverse thinking)

Building the graph is the real work:

• Minimum Height Trees (topo-sort-like peeling from the leaves inward)
• Alien Dictionary (construct edges from word comparisons, then sort)
• Sequence Reconstruction (verify a unique ordering exists, exactly one zero in-degree node at each step)

Harder combinations:

• Parallel Courses (topo sort plus level counting for minimum semesters)
• Course Schedule IV (reachability queries layered on top of ordering)
• Sort Items by Groups Respecting Dependencies (two-level topo sort, groups and items)
• Build a Matrix With Conditions (topo sort on both rows and columns)

The bar:

• Finish "Sort Items by Groups Respecting Dependencies" cleanly, with correct cycle handling at both levels, and you understand this pattern at an interview level.

9Where this shows up (which companies/rounds lean on it)#

It is a favorite at companies with real dependency systems:

• Build tooling, package managers, data pipelines, and scheduling.
• Google and Meta ask the course-schedule family often in the graph portion of an onsite.
• Amazon leans toward the dependency and build-order framing, which maps straight onto how their internal build systems work.
• It also folds into system design discussions about task orchestration and job scheduling, where the interviewer wants you to name the DAG out loud and explain how you would detect cycles in a pipeline before it deadlocks in production.

It is a medium topic that rewards precision.

• The algorithm is short, maybe 15 lines.
• The points are won or lost on three things: edge direction, cycle detection, and seeding the queue with every zero in-degree node.
• Nail those three and this becomes one of the most reliable problems you can get.

The sort is 15 lines of muscle memory. The round is won on edge direction, the cycle check, and seeding every zero.

Want to know which rounds at a specific company lean on graph patterns like this? Check our company guides to see where topological sort shows up.