Scanning building heights with a monotonic stack, why is the widest rectangle capped by a bar computed only when that bar is popped?
answer
- A rectangle needs two edges
- One edge only arrives from the right
- Ask what the bar underneath means
- Left edge is one past the new top
- Width is i minus new top minus one
basics
~20 sA rectangle needs both edges. The right edge stays unknown until a shorter bar arrives, and that arrival is exactly what triggers the pop; the left edge is the bar left underneath on the stack. Only at pop time are both known.
solid answer
~40 sThe stack holds indices of bars whose heights increase from bottom to top. When the bar at index `i` is shorter than the top, the popped bar `j` can never extend further right, so its full rectangle is finally settled: height `h[j]`, right boundary `i - 1`, and left boundary one past whatever index is now on top — that survivor is the nearest shorter bar to the left. The width is therefore `i - top(stack) - 1`, or `i` when the stack empties, meaning `h[j]` spanned the entire prefix. At push time none of this is knowable: the bar might extend one column or five hundred. So the scan settles one full rectangle per bar, each at the single moment both of its blocking bars are known, and keeps the largest area seen.
code
pseudocode · 12 linesstack = empty // indices; heights increase bottom to top
best = 0
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)
... // bars still stacked here are unresolvedgo deeper
Be ready to explain the reframing: every rectangle is limited by its shortest bar, so it is enough to ask how far each bar can stretch left and right at its own height.
Walk through one pop out loud — which index gives the right boundary, which gives the left, and where the minus one comes from. Do not recite the formula without naming both boundaries.
Demonstrate the invariant behind the code (open rectangles, increasing heights, left boundary is the entry below) so you can reconstruct the loop and defend the tie rule instead of recalling a memorised snippet.
Own when this scan is worth it at all. On short silhouettes the quadratic double loop is trivially reviewable; argue the switch on measured input sizes, and make sure whoever maintains it can restate the invariant.
## The shape of the question Given a contiguous run of building heights forming a skyline silhouette, you want the widest banner that fits underneath — a solid axis-aligned rectangle. Any such rectangle is limited by its shortest bar, so it is enough to ask, for every bar: *how far left and right can a rectangle of exactly this bar's height stretch before it is blocked?* That reframing is what makes the monotonic stack apply, and stating it out loud is half the answer. A rectangle of height `h[j]` extends rightwards until the first bar strictly shorter than `h[j]`, and leftwards until the first bar shorter than `h[j]` on that side. Both are "nearest smaller" boundaries — and the eviction discipline of a height-increasing stack hands them to you. ## Why push time knows nothing When index `j` is pushed, everything to its right is unread. The bar could be the start of a long plateau or be cut off by the very next column. There is no number to record and no partial answer to accumulate: the width is undetermined, not merely unrefined. The scan therefore defers, and the deferral is the mechanism, not an optimisation. ## What a pop settles, precisely A pop of `j` happens when a bar `i` arrives with `h[i]` no greater than `h[j]`. Two facts land simultaneously: - **Right boundary.** `i` is the first index after `j` with a height that stops the rectangle, so the rectangle's last column is `i - 1`. - **Left boundary.** The index now on top of the stack, call it `l`, is the nearest index before `j` with a smaller height. Everything between `l` and `j` was already popped by `j` itself or by something between, which means all of it is at least `h[j]` tall — so the rectangle passes over it freely. The rectangle's first column is `l + 1`. Hence `width = (i - 1) - (l + 1) + 1 = i - l - 1`, and `area = h[j] * width`. **The single most common wrong answer is `i - j`** — using the popped bar's own index as the left edge. That silently discards the entire left extension, and it is a plausible-looking bug because it produces correct answers on inputs where every bar is blocked immediately on its left. ## The empty-stack case If the stack is empty after popping `j`, no bar to the left of `j` is shorter, so the rectangle runs from column 0 to `i - 1`: `width = i`. Missing this branch is the second classic defect, and it costs you exactly the tall-bar-early inputs. A common cure is to pre-push a virtual floor bar at index `-1` whose height is below every real height; the width formula `i - top(stack) - 1` then holds unconditionally, because the stack can never empty. ## Ties Popping on "shorter than" versus "shorter than or equal" changes intermediate widths but not the maximum. With equal-height neighbours, one variant truncates the earlier duplicate's width at the later one and lets the last member of the run measure the full plateau; the other does the reverse. Either way at least one bar of each equal-height run measures the plateau's full span, so the maximum area is unaffected. It matters only if the scan must report a correct width *per bar* rather than the single best area — a distinction worth naming, because interviewers use it to separate memorised code from understood code. ## Reading the invariant back The stack's invariant is: *the indices on it are the bars whose rectangles are still open, in increasing height, and each one's left boundary is the index below it.* Every pop closes exactly one open rectangle with the boundaries the invariant guarantees. If you can state that sentence, you can rebuild the loop from scratch under interview pressure instead of recalling `-1`s. ## Where the loop is easy to get wrong Three defects account for nearly every failing submission: the left boundary taken as the popped index; the empty-stack width forgotten; and the bars still on the stack when the loop ends never being resolved at all. The third is invisible on inputs that happen to end with a short bar and catastrophic on a rising skyline — which is why the flush is treated as part of the algorithm rather than as cleanup.
- Why is the left boundary the bar left underneath, and not the popped bar's own index?The bar underneath is the nearest shorter bar to the left of the popped one; everything between them was popped by the popped bar itself, so it is at least as tall and the rectangle passes over it. Using the popped bar's own index gives `i - j`, which throws away the whole left extension and quietly under-reports the area.
- You pop on shorter-or-equal rather than strictly shorter — does the reported maximum change?No. On a run of equal heights one variant truncates the earlier duplicates and lets the last measure the full plateau, the other does the reverse; in both, some member of the run measures the full span, so the maximum area is identical. The difference matters only if you need a correct width for every individual bar.
- The stack empties while popping — what width does that bar get?The full prefix, `i`: no shorter bar exists to its left, so the rectangle starts at column 0 and ends at `i - 1`. Rather than special-casing it, many implementations pre-push a virtual floor bar shorter than every real bar at index `-1`, which makes `i - top(stack) - 1` correct unconditionally.
Measuring how far a fence panel can stretch: you cannot record its span when you plant it, only when you hit the posts on both sides — and the near post is whichever one you had already planted underneath.
saying these in an interview costs you the question
- Says the rectangle is settled when the bar is pushed
- Uses the popped bar's own index as the left edge
- Claims the width is always i minus the popped index
- Forgets the empty-stack full-prefix width
- Rescans left from each bar to find its boundary