Loading page…
Practice problem · easy
You work on a build tool for an app. A project has n build steps, numbered 0 to n - 1. Some steps need others to finish first: the code is compiled before it is bundled, and bundled before it is published.
The tool runs one step at a time. When several steps are ready, it runs the one with the smallest number, so two runs of the same project give the same order. If the needs loop, no order exists.
Write build_order(n, needs).
n is the number of steps.needs[i] = [step, required] means step cannot start until required has finished.n steps in the order they run. At each point, run the smallest step that is ready.[] when no order exists.Input: n = 4, needs = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]Steps 1 and 2 need step 0. Step 3 needs both 1 and 2. Kahn's algorithm keeps the ready steps in a heap.
| Round | Ready (heap) | Take | Order so far |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 1, 2 | 1 | 0, 1 |
| 3 | 2 | 2 | 0, 1, 2 |
| 4 | 3 | 3 | 0, 1, 2, 3 |
After step 1 runs, step 3 still needs step 2, so only 2 is ready in round 3.
Input: n = 3, needs = [[0, 1], [1, 2], [2, 0]]
Output: []Step 0 needs 1, step 1 needs 2, and step 2 needs 0. Every step waits for another one, so none is ready at the start and no order exists.
Input: n = 3, needs = []
Output: [0, 1, 2]No step needs anything. All three are ready, and the smallest goes first each time.
1 ≤ n ≤ 100,0000 ≤ len(needs) ≤ 100,000, and every row is [step, required] with 0 ≤ step, required < n and step ≠ requiredThere can be 100,000 steps and 100,000 needs. A method that scans all the steps every time one runs does n × (n + m) work: about 20 billion steps. That is too slow, so the answer has to touch each step and each need only a few times. Counting needs and keeping the ready steps in a heap does (n + m) log n: a few million steps.
build_order · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.