</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Topological sort 301: recipes-from-supplies and items-within-groups pipelines

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],[],[],[]]

Sort items by groups, two-level topological worked example

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] == -1 instead 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

  1. Building the graph is the problem. Kahn's algorithm itself is the same short loop every time.
  2. Edges point from what you have to what it unlocks, which makes indegree the count of what is still missing.
  3. Dissolve special cases into the general rule. A private group per ungrouped item removes a whole 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. Cycles come free with Kahn's: fewer nodes emitted than exist. Recipes keeps the partial result, Sort Items returns [].
  7. 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.

Find All Possible Recipes from Give

Core idea: Point the edges from ingredient to recipe ("having this unlocks that"), so a recipe's indegree is the number of ingredients it needs. Seed Kahn's queue with the supplies you already hold and decrement as you go. When a recipe's indegree reaches zero it can be made, and the line that matters is pushing it back into the queue, because a finished recipe is itself an ingredient for others. Cycles need no detection code: two recipes that need each other never reach indegree zero and are never emitted. O(V + E).

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.