Topological Sort

What is this?

Kahn's algorithm is assumed by 301. What is being tested is whether you can build the right graph to run it on. In Find All Possible Recipes the nodes are strings and two different kinds of thing — supplies you already have and recipes you can make. In Sort Items by Groups there are two orderings at once, items among themselves and groups among themselves, and they must agree.

💡 Fun fact: Sort Items by Groups Respecting Dependencies looks like it needs a special case for items belonging to no group — group[i] == -1. It does not. Give each of those items its own brand-new group and every one of them becomes an ordinary group of size one. The two-level algorithm then runs unchanged, and the special case disappears entirely. Turning an exception into an instance of the general rule is one of the highest-value moves in a whiteboard interview.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: decide what a node is and which way the edges point, and Kahn's algorithm is eight lines. Both problems are won or lost before the traversal starts.

1. Nodes that are strings, of two kinds

Edges run from ingredient to recipe — "having this unlocks that" — and a recipe's indegree is simply how many ingredients it needs:

adj = defaultdict(list)
indeg = {r: len(ing) for r, ing in zip(recipes, ingredients)}
for r, ing in zip(recipes, ingredients):
    for x in ing:
        adj[x].append(r)

q, out = deque(supplies), []                   # seed with what you already have
while q:
    u = q.popleft()
    for r in adj[u]:
        indeg[r] -= 1
        if indeg[r] == 0:                      # every ingredient now available
            out.append(r); q.append(r)         # a made recipe is itself an ingredient
return out

The line that matters is q.append(r): a finished recipe goes back into the queue because it can be an ingredient for another. And note what happens to a cycle — two recipes each needing the other never reach indegree zero, so they are simply never emitted. Cycle detection is free; there is nothing extra to write.

2. Two levels of ordering

for i in range(n):                             # the special case, dissolved
    if group[i] == -1:
        group[i] = m; m += 1

for i in range(n):
    for b in beforeItems[i]:
        item_edge(b, i)
        if group[b] != group[i]:
            group_edge(group[b], group[i])     # a cross-group dependency orders the groups

group_order = topo(range(m), ...)
item_order  = topo(range(n), ...)
if not group_order or not item_order: return []          # a cycle at either level

An item_order filtered into per-group buckets is already correct within each group, because a topological order restricted to a subset stays topological. So the final answer is: order the groups, then emit each group's items in the order they appeared in the global item sort. Two sorts, one concatenation.

An empty result from either sort means a cycle, and the problem asks for an empty list in exactly that case — so the failure mode of Kahn's algorithm is the required output.

3. A 30-second worked example (two levels)

n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]

dissolve -1:   items 0,1,7 become groups 2,3,4     → groups 0..4

cross-group edges:
  6 before 1   group 0 → group 3
  5 before 2   group 1 → group 1   (same group — no group edge)
  6 before 3   group 0 → group 0   (same group — no group edge)
  6 before 4   group 0 → group 0   (same group)
  3 before 4   group 0 → group 0   (same group)

group order:   0, 1, 2, 4, 3        (0 must precede 3; the rest are free)
item order:    6, 3, 4, 5, 2, 0, 7, 1
bucketed:      g0=[6,3,4]  g1=[5,2]  g2=[0]  g4=[7]  g3=[1]

result: [6, 3, 4, 5, 2, 0, 7, 1]

Only one dependency crosses a group boundary — item 6 before item 1 — and it alone forces group 0 ahead of group 3. Every other edge lives inside group 0 and is handled by the item-level sort. Several valid orders exist; the problem accepts any.

4. Where you'll actually meet this

• Build systems. Recipe resolution is dependency resolution, with supplies as the already-built artefacts.
• Package managers. Installing in dependency order, with a cycle reported rather than looped on.
• Monorepo release ordering. Packages within a team's area must ship together, and areas have an order between them — the two-level problem exactly.
• Course and curriculum planning. Prerequisites within a subject, and subjects with an order among themselves.
• Data pipeline scheduling. Tasks grouped by stage, where stages are sequential and tasks within a stage are partially ordered.

5. Problems in this chapter

▶ Find All Possible Recipes from Given Supplies

Return every recipe that can be created. Point edges from ingredient to recipe, seed the queue with the supplies, and feed each finished recipe back in.
Pattern: Kahn's algorithm on string nodes. Target: O(V + E) time and space.

▶ Sort Items by Groups Respecting Dependencies

Order items so grouped items stay adjacent and all dependencies hold. Give ungrouped items private groups, sort the groups, sort the items, then concatenate.
Pattern: two composed topological sorts. Target: O(V + E) time and space.

6. Common pitfalls 🚫

• Pointing the edges backwards. From ingredient to recipe, not the reverse — the direction decides what indegree means.
• Not feeding a completed recipe back into the queue. Recipes are ingredients for other recipes.
• Special-casing group[i] == -1 instead of allocating a private group and deleting the branch.
• Adding a group edge for a same-group dependency, which creates a self-loop and makes every group order impossible.
• Sorting items only within their group. Cross-group edges must also constrain the item order.
• Not detecting the cycle. An output shorter than the node count is the signal, and here it is the required answer.
• Assuming a unique answer. Both problems accept any valid order, and saying so saves you defending an arbitrary choice.

7. Key takeaways

1. Building the graph is the problem. Kahn's algorithm itself is the same eight lines every time.
2. Edges point from what you have to what it unlocks, which makes indegree "how much is still missing".
3. Dissolve special cases into the general rule — a private group per ungrouped item removes an entire branch.
4. Two levels of ordering means two sorts, and a global item order restricted to one group is still valid.
5. A same-group dependency must not become a group edge, or you build a self-loop.
6. Cycle detection comes free with Kahn's: fewer nodes emitted than exist.
7. Why interviewers like it: the algorithm is standard, so the entire conversation is about modelling — which is exactly what they want to hear.

Order: Find All Possible Recipes from Given Supplies → Sort Items by Groups Respecting Dependencies.