Largest Rectangle in Histogram

Remember A5's cascade pop? One warm day resolved four waiting days. Histograms work the same way — but with a twist: you need the width.

Here is a histogram with 6 bars: 215623. Tap a bar and find the largest rectangle that includes it. Then do the same for the next bar. And the next.

In Daily Temperatures (A5), every pop answered a DISTANCE question: “how many days until warmer?” Here the pop must compute an AREA — and the width formula is where this problem bites back. The stack itself is familiar. The formula is the trap.

— The move:You will extend a few bars by hand to feel the cost, then watch a single cascade find all the rectangles at once. Along the way you will meet i - poppedIdx and i - stack.peek() - 1 — two formulas that look the same and aren't.