Why is a monotonic-stack next-greater scan O(n) when a while loop sits inside the for loop?
answer
- count total work, not per-step work
- how many times can one index be popped
- how many pushes happen in the whole scan
- each index enters once, leaves once
- inner iterations bounded by total pushes
basics
~20 sEvery index is pushed exactly once and popped at most once, so the inner while loop runs at most n times in total across the scan. Total work is linear even though one step may pop many indices.
solid answer
~50 sNesting a loop does not multiply the cost unless the inner loop can do fresh work each time the outer one turns. Here it cannot: the inner loop only pops, each index enters the stack exactly once, and a popped index never returns. So the total number of inner iterations over the entire scan is bounded by the total number of pushes, which is n. Add the n outer steps and the work is `O(n)` time with `O(n)` auxiliary space for the stack. This is an amortized bound, not an average-case one — it holds for every input, including the adversarial ones. It also does not promise any individual step is cheap: on a run of decreasing scores followed by one huge score, that single step pops nearly everything. The expensive step is paid for by the cheap steps that pushed those entries.
code
pseudocode · 10 linesstack = empty // holds indices, scores non-increasing
for i in 0..n-1:
ans[i] = NONE
for i in 0..n-1:
while not empty(stack) and score[top(stack)] < score[i]:
j = pop(stack)
ans[j] = i // i is the nearest higher score after j
push(stack, i)
...
// indices still in stack keep ans = NONEgo deeper
Recall the one-line reason: each index is pushed once and popped at most once, so the inner loop runs at most n times overall. Being able to say that beats reciting exponents.
Explain the counting argument and trace an input where one step pops many entries, showing that the burst was financed by the cheap steps before it.
Be precise that the bound is amortized worst-case rather than average-case, and note that a per-record latency budget still sees the burst even though throughput is linear.
Own the call of when the linear-space stack version is worth it at all: on small or near-increasing inputs the naive forward scan can win on constants and memory locality, and that crossover should be measured, not assumed.
## The misread the question aims at Seeing `for` wrapped around `while`, most people multiply: n outer steps times up-to-n inner steps equals `O(n^2)`. That reasoning is valid only when the inner loop can perform up-to-n *fresh* units of work on every outer step. The monotonic stack scan defeats it because the inner loop consumes a resource that the outer loop produces exactly once per element. ## The counting argument, in full Fix the leaderboard snapshot of n score records. Two facts about the code: - **Pushes:** the outer loop body ends with exactly one push, so there are exactly n pushes over the whole run. - **Pops:** every iteration of the inner loop performs exactly one pop, and a popped index is never pushed again — it has its answer and is finished. A pop requires a matching earlier push, so the number of pops over the entire scan is at most n. Since inner iterations and pops are in one-to-one correspondence, the inner loop body executes at most n times **in total, across all outer iterations** — not per outer iteration. Total operations: at most n outer steps plus at most n inner steps plus constant work each, hence `O(n)` time. The stack can hold at most n indices, so auxiliary space is `O(n)`. Notice where the argument lives: not in any single step, but in the sum over the sequence. That is what makes the bound amortized. ## Two extreme inputs, traced **Strictly decreasing scores** (900, 800, 700, …). No pop ever fires, because the top is always larger than the arriving score. Each step is `O(1)`; the stack grows to n; nothing is ever answered. Total inner iterations: zero. **Strictly increasing scores** (100, 200, 300, …). Every step pops exactly one index — the single element pushed the step before — and then pushes. Each step is `O(1)`; the stack never exceeds one entry. Total inner iterations: n-1. **Decreasing then one spike** (900, 800, 700, …, 100, 9999). The first n-1 steps pop nothing and the stack grows to n-1. The final step pops all n-1 entries in one burst. That single step costs `Θ(n)` — and the bound still holds, because those n-1 pops were financed by n-1 preceding steps that each did a single cheap push. This is the input that convinces a skeptical interviewer: the worst *step* is linear, the worst *total* is linear. ## Amortized is not average-case An amortized bound says: over any sequence of operations, including the worst sequence an adversary can choose, the total cost divided by the number of operations is `O(1)` per operation. An average-case bound instead assumes a probability distribution over inputs and reports the expectation. The distinction matters because the linear bound here needs no assumption about the data at all — sorted, reversed, duplicate-heavy, adversarial, it is still one push and at most one pop per index. Saying "it's O(n) on average" understates the guarantee and is one of the more reliable ways to lose the point. Equally, it does not promise per-step cheapness. If the workload has a latency budget per record, the burst behaviour is real and must be measured; the amortized bound is about throughput over the batch. ## Comparing against the naive scan The forward-scan-from-every-position approach is `O(n^2)` worst-case and `O(1)` extra space; it is also `O(n)` on inputs where the very next element usually answers, which happens on near-increasing data. So the stack version's win is on the worst case and on adversarial or decreasing data — it trades `O(n)` auxiliary space for a bound that does not depend on the input shape. On a small board, the naive version can genuinely be faster because its constant factor is smaller and it touches memory linearly; asymptotic superiority promises nothing at small n. Knowing where the crossover is for your data size is a better answer than reciting the exponents. ## How to say it in an interview "There is a while inside the for, but the while only pops, and each index can be popped at most once because it is pushed exactly once. So the inner loop runs at most n times in total, not n times per step — the whole scan is `O(n)` time and `O(n)` space, and that is an amortized worst-case bound, not an average." Two sentences and a trace of the spike input is the entire expected answer.
- Give an input where one iteration pops almost everything, and say why the bound survives.A long run of decreasing scores followed by one very high score: the final step pops n-1 indices in a burst and costs linear time by itself. The bound survives because those n-1 pops correspond to n-1 earlier steps that each did only a push. Total pops over the scan is still bounded by total pushes, which is n.
- Is this an amortized bound or an average-case bound, and why does the difference matter?Amortized. It bounds the total cost over a worst-case sequence with no assumption about the input distribution, so decreasing, duplicate-heavy or adversarial data all still give linear total time. An average-case claim would assume a distribution and would say nothing about the adversarial case. The amortized claim is strictly stronger here.
- What is the auxiliary space, and which input maximises it?O(n) for the stack, plus O(n) for the answers. A strictly decreasing sequence maximises the stack: nothing is ever popped during the scan, so all n indices are resident at the end. On strictly increasing input the stack never exceeds one entry, which is why measured memory on real data can be far below the bound.
saying these in an interview costs you the question
- Concludes O(n^2) because a while loop is nested in a for loop
- Says amortized means average over random inputs
- Claims the worst case is quadratic on decreasing input
- Asserts every single step is O(1)
- Omits the O(n) stack space from the analysis