Why can a monotonic-stack scan over strictly increasing bar heights return 0 unless a sentinel bar is appended?
answer
- Ask when an answer is actually written
- Rising input triggers no eviction
- The loop ends with a full stack
- Survivors deserve right boundary n
- Append a bar shorter than all others
basics
~20 sRectangles are settled only when a bar is popped, and a strictly rising skyline never triggers a pop. The loop ends with every bar still stacked and nothing measured, so the running best keeps its initial value.
solid answer
~50 sThe scan resolves a bar's rectangle at pop time, and a pop happens only when a shorter bar arrives. On a monotonically rising run of heights no bar is ever shorter than the stack top, so the loop pushes every index and pops none; the answer variable is returned untouched. Two equivalent cures exist. Append a virtual bar shorter than every real height at index `n` — it pops the entire stack with right boundary `n - 1`, exactly the boundary those bars deserve. Or drain the stack explicitly after the loop, using `i = n` in the same width formula. Many implementations also prepend a floor bar strictly shorter than every real bar, which removes the empty-stack branch. Forgetting the flush is invisible on inputs that happen to end low and catastrophic on a rising one.
code
pseudocode · 12 linesbest = 0
stack = empty // indices; heights increase
for i in 0..n-1
while not isEmpty(stack) and h[top(stack)] >= h[i]
j = pop(stack)
if isEmpty(stack)
width = i
else
width = i - top(stack) - 1
best = max(best, h[j] * width)
push(stack, i)
return best // survivors on the stack were never measuredgo deeper
Remember that this scan writes its answers when bars are removed, so an input that never removes anything produces no answers at all. Know that a shorter bar appended at the end fixes it.
Explain which right boundary the surviving bars deserve and why it is n rather than n minus one, and show that appending a sentinel and draining after the loop are the same fix spelled two ways.
Turn it into a review habit: in any scan that produces answers on eviction, check that every pushed entry is guaranteed to be evicted, and pick sentinel values that stay outside the real value range.
Decide which spelling the codebase standardises on. A sentinel keeps one code path and one width formula, which matters more for long-term correctness than the micro-cost of the extra element; make it the house pattern and say why.
## The bug, stated exactly The pop-time discipline says: a bar's rectangle is measured when a shorter bar arrives and evicts it. That rule is complete only if every bar is eventually evicted. Nothing in a plain `for i in 0..n-1` loop guarantees that. On a skyline whose heights only rise, the eviction condition is never satisfied, every index is pushed, and the loop exits with a full stack of bars whose rectangles were never computed. The function returns whatever the running best was initialised to — typically 0. This is a **boundary bug, not a performance bug**, and it survives casual testing because most hand-made examples end with a dip. It fails on the simplest possible input, a rising run. ## The right boundary those survivors deserve A bar still on the stack when the input is exhausted was never blocked on the right, so its rectangle extends to the last column, `n - 1`. In the width formula the arriving index plays the role of "first blocked column", so the survivors should be resolved with `i = n`. That yields: - `width = n - top(stack) - 1` when something remains beneath, and - `width = n` when the stack empties. Writing `n - 1` instead is the natural second mistake — an off-by-one that shortens every surviving rectangle by one column, most visibly on the tallest bar of a rising skyline. ## Two spellings of the same fix **Append a right sentinel.** Treat the input as having one extra bar at index `n` whose height is below every real height. Because it is shorter than everything, it evicts the whole stack, and the arriving index is `n` automatically. The loop body needs no change at all: the flush is expressed entirely in the data. This is the version that reads best, because the algorithm keeps exactly one code path. **Drain after the loop.** Repeat the pop body with `i = n` until the stack is empty. Functionally identical, but the width formula now appears twice, which is where the `n` versus `n - 1` divergence tends to creep in during a refactor. ## The left sentinel is a different fix Prepending a floor bar strictly shorter than every real bar solves a separate problem: the empty-stack branch. With a floor permanently at the bottom, the stack can never empty during the main loop, so `width = i - top(stack) - 1` is unconditionally correct and the `if isEmpty` branch disappears. The two sentinels are independent — one removes the missing-flush class of bug, the other removes the missing-branch class. ## Choosing sentinel heights carefully "Use 0" is the usual advice, and it is safe for the **right** sentinel whenever real heights are non-negative and the pop rule evicts on equal heights: a zero-height bar then flushes everything, and even a genuine zero-height bar in the input contributes zero area, so nothing is lost. It is **not** automatically safe for the **left** floor. If real heights may be 0 and the pop rule evicts on equal, a genuine zero-height bar can pop the floor itself, the stack empties, and the branch you deleted is suddenly needed again. The floor must be strictly below every attainable height — a virtual `-1`, or an index-based special case. Interviewers who ask "can heights be zero?" are usually probing exactly this. ## How to spot it in review The diagnostic is mechanical: **for every index pushed, is there a guaranteed pop?** If the only pop site is inside the arrival loop, and the loop's condition can be false for the whole input, the answer is no and the scan is incomplete. The same check catches the same defect in every pop-time-resolution scan, not just this one — whenever an answer is written at eviction, unevicted entries are unanswered entries. ## What to say in the interview Name the failure before writing the loop: *"answers are produced on pop, so I need every bar to pop; I'll append a bar shorter than all of them so the flush is part of the scan."* That single sentence pre-empts the follow-up and shows you reason about termination conditions rather than pattern-matching a snippet.
- You drain the stack after the loop instead of appending a sentinel — what index plays the role of the arriving bar?`n`, one past the last real bar, because a survivor was never blocked and its rectangle reaches the final column `n - 1`. Using `n - 1` shortens every surviving rectangle by one column. The sentinel spelling avoids the question entirely: the extra bar sits at index `n`, so the existing formula already uses the right value.
- Why would you also prepend a floor bar on the left?To delete the empty-stack branch. With a bar strictly shorter than every real height permanently at the bottom, the stack never empties during the scan, so `width = i - top(stack) - 1` is unconditionally correct. It fixes a different defect from the right sentinel — a missing branch rather than a missing flush.
- Real heights can legitimately be zero — is a zero-height sentinel still safe?As a right sentinel, yes: it evicts everything, and a genuine zero-height bar has zero area, so nothing is lost. As a left floor, no: with an evict-on-equal rule a real zero-height bar can pop the floor, the stack empties, and the branch you removed is needed again. Use a value strictly below every attainable height.
A shop that only rings up a customer when the next one steps forward. If nobody else comes in, the last customer stands there forever and the till reads zero — so you add a closing bell.
saying these in an interview costs you the question
- Calls a rising skyline the easy case
- Claims the tallest bar is measured on the way up
- Omits the drain after the main loop
- Uses n minus one as the flush boundary
- Picks a sentinel height equal to a real bar