Topological Sort
What is this?
Kahn's algorithm is assumed at this level. 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 of two kinds, 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 becomes an ordinary group of size one. The two-level algorithm then runs unchanged and the special case disappears. Turning an exception into an instance of the general rule is a useful move on a whiteboard.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: decide what a node is and which way the edges point, and Kahn's algorithm is a short loop. 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 how many ingredients it still lacks. The lesson also shows the simpler fixed-point sweep (rescan every recipe until a pass adds nothing), which is O(n * E) and worth naming before moving to Kahn's, which is O(V + E).
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. Two cases need no extra code. Two recipes that each need the other never reach indegree zero, so neither is emitted. An ingredient that is neither a supply nor a recipe is never popped, so anything needing it stays stuck. In this problem the output is simply whatever was made, so a short result is a normal answer and not an error.
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
Run one topological sort over all items, drop the items into per-group buckets in that order, and each bucket is already correct within its group, because a topological order restricted to a subset stays topological. Then emit the buckets in group order. Two sorts, one concatenation.
A cycle in either sort means the answer is an empty list, which is exactly what the problem asks for. The group graph can have a cycle even when the item graph does not: item 2 before item 0 puts one team first, item 1 before item 3 puts the other first, and no item-level edge loops. Only the group sort catches it.
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],[],[],[]]
Items 0, 1 and 7 have no group, so they become groups 2, 3 and 4. Only one dependency crosses a group boundary: item 6 before item 1, which puts group 0 ahead of group 3. The other edges (5 before 2, 6 before 3, 3 and 6 before 4) stay inside group 1 or group 0 and are handled by the item-level sort. Several valid orders exist, and the problem accepts any.
4. Where you'll actually meet this
- Build systems. A target builds once its inputs exist, and a built target is an input to others. Source files play the role of supplies.
- Package managers. Installing in dependency order, with a cycle or a missing dependency leaving the package uninstalled.
- Batched release ordering. Services owned by one team ship back to back, and teams have an order between them, which is the two-level problem.
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. Recipes behind a cycle or an unknown ingredient are simply left out.
Pattern: Kahn's algorithm on string nodes. Target: O(V + E) time and space, where V counts recipes and supplies and E the ingredient entries.
Sort Items by Groups Respecting Dependencies
Order items so each group stays contiguous and all dependencies hold. Give ungrouped items private groups, sort the groups, sort the items, then concatenate the buckets.
Pattern: two composed topological sorts. Target: O(n + m + E) time and space, where m includes the private groups and E is the total length of the beforeItems lists.
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] == -1instead of allocating a private group and deleting the branch. - Adding a group edge for a same-group dependency. It creates a self-loop and makes every group order impossible.
- Trying one item sort and then gathering each group. Pulling a group's items together can move an item ahead of something it depends on. Sort the groups too.
- Checking only the items for a cycle. The items can be acyclic while the groups contradict each other.
- Treating a short output as an error in Recipes. There it is the answer. In Sort Items a short Kahn run means return
[]. - Assuming a unique answer. Both problems accept any valid order.
7. Key takeaways
- Building the graph is the problem. Kahn's algorithm itself is the same short loop every time.
- Edges point from what you have to what it unlocks, which makes indegree the count of what is still missing.
- Dissolve special cases into the general rule. A private group per ungrouped item removes a whole branch.
- Two levels of ordering means two sorts, and a global item order restricted to one group is still valid.
- A same-group dependency must not become a group edge, or you build a self-loop.
- Cycles come free with Kahn's: fewer nodes emitted than exist. Recipes keeps the partial result, Sort Items returns
[]. - Why interviewers like it: the algorithm is standard, so the conversation is about modelling.
Order: Find All Possible Recipes from Given Supplies, then Sort Items by Groups Respecting Dependencies.