Flat-Pack Assembly Order
You bought a wardrobe that comes in a flat box. The manual is a mess: instead of numbered pages, it has n steps, numbered 0 to n - 1, and a list of rules like [3, 5], meaning step 3 must be done before step 5 (you cannot hang the doors before the hinges are on).
You want a single order to do all the steps in that breaks no rule. Sometimes the manual contradicts itself, for example step 1 before step 2 and step 2 before step 1. Then no order exists, and you would rather know before you start.
Your task
Write assemblyOrder(n, rules). Return a list containing every step from 0 to n - 1 exactly once, such that for every rule [a, b], step a comes before step b.
If several orders work, return any of them. If no order works, return an empty list [].
assemblyOrder(n: int, rules: int[][]) → int[] Several answers can be correct; any valid one is accepted.
Examples
n = 4 rules = [[0, 2], [1, 2], [2, 3]]
[0, 1, 2, 3]
Step 2 needs both 0 and 1 done first, and step 3 needs 2. So 0 and 1 go first in either order, then 2, then 3. [1, 0, 2, 3] is also accepted.
n = 3 rules = [[0, 1], [1, 2], [2, 1]]
[]
Step 1 must come before 2, and 2 before 1. No order can do both, so return [].
Constraints
- 1 ≤ n ≤ 2,000
- 0 ≤ rules.length ≤ 5,000
- 0 ≤ a, b < n and a ≠ b
- The same rule may appear more than once
Start with brute force
Try every ordering of the steps and return the first that breaks no rule.
There are n! orderings. Even 12 steps give about 479 million of them, and n can be 2,000. The rules tell you directly which steps can go next, so there is no need to guess.
Hints
0 of 4 shown- Hint 1
In the first example, which steps could you do right now, before anything else? What do they have in common?
- Hint 2
A step is ready when no rule says some other unfinished step must come before it. Doing a ready step may make other steps ready.
- Hint 3
For each step, count how many rules point into it: how many steps it is still waiting on. When you finish a step, which counts go down?
- Hint 4
Count incoming rules for each step. Put every step with count 0 in a queue. Repeatedly take one out, add it to the order, and lower the count of each step it points to; any count that hits 0 joins the queue. If the order ends up shorter than
n, the leftover steps are stuck waiting on each other in a loop: return [].
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Think of the rules as arrows between steps. A step can go next once every arrow into it comes from a finished step. So keep, for each step, a count of arrows still pointing into it, and always pick from the steps whose count is 0. This is Kahn's algorithm for topological sorting.
Trace the first example, rules 0→2, 1→2, 2→3. Waiting counts: step 0 = 0, step 1 = 0, step 2 = 2, step 3 = 1. Queue: 0, 1.
- Take 0. Order: [0]. Step 2's count drops to 1.
- Take 1. Order: [0, 1]. Step 2's count drops to 0, so 2 joins the queue.
- Take 2. Order: [0, 1, 2]. Step 3's count drops to 0, so 3 joins.
- Take 3. Order: [0, 1, 2, 3]. All 4 steps placed.
In the second example, steps 1 and 2 each wait on the other. Only step 0 starts at count 0. After taking it, step 1 still waits on step 2, so the queue runs dry with 1 of 3 steps placed. A short order means a loop, so return [].
Duplicate rules are harmless: a repeated arrow adds 1 to the count twice and is removed twice, once per copy in the list.
function assemblyOrder(n, rules) {
const next = Array.from({ length: n }, () => []);
const waiting = new Array(n).fill(0); // rules still pointing into each step
for (const [a, b] of rules) {
next[a].push(b);
waiting[b]++;
}
const queue = [];
for (let s = 0; s < n; s++) if (waiting[s] === 0) queue.push(s);
const order = [];
for (let head = 0; head < queue.length; head++) {
const step = queue[head];
order.push(step);
for (const after of next[step]) {
waiting[after]--;
if (waiting[after] === 0) queue.push(after); // now ready
}
}
return order.length === n ? order : []; // leftovers are stuck in a loop
}from collections import deque
def assembly_order(n, rules):
nxt = [[] for _ in range(n)]
waiting = [0] * n # rules still pointing into each step
for a, b in rules:
nxt[a].append(b)
waiting[b] += 1
queue = deque(s for s in range(n) if waiting[s] == 0)
order = []
while queue:
step = queue.popleft()
order.append(step)
for after in nxt[step]:
waiting[after] -= 1
if waiting[after] == 0:
queue.append(after) # now ready
return order if len(order) == n else [] # leftovers are stuck in a loopRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.