Canonical Deep-Dive: Largest Rectangle in Histogram

Problem: Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram/) The lesson: the monotonic stack, and that the real work happens on the pop, not the push.

This is a guided walk-through, not an answer key. It explains how to think about the monotonic stack: what goes on it, when you pop, what you compute when you pop, and why the sentinel-zero trick saves you a second loop. It shows the recurrence of the idea as a relation and a pseudocode skeleton, and stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given a list heights where each entry is the height of a bar of width 1, all sitting on a common baseline. Find the area of the largest rectangle that fits entirely inside the histogram. A rectangle can span several adjacent bars, but its height is limited by the shortest bar it covers.

Why the brute force is too slow

The most direct idea: for every pair of bars treat them as the left and right edge of a rectangle, and the height is the minimum bar between them. That is O(n^2) pairs (or O(n^3) if you re-scan for the minimum each time). A cleaner brute force fixes each bar as the rectangle’s height and expands left and right while neighbors are at least as tall, which is still O(n^2) in the worst case (a sorted histogram makes every expansion run the full length).

Have this baseline in your head; it is what the stack improves on. The slowness comes from re-scanning to find, for each bar, “how far left and right can I extend before I hit something shorter.” That phrase, “how far until something shorter,” is the monotonic-stack cue from this week.

The reframe that unlocks it

Stop thinking about rectangles by their left and right edges. Instead, ask one question for each bar: “if this bar is the limiting (shortest) height of a rectangle, how wide can that rectangle be?” Every rectangle in the histogram has some bar as its shortest bar, so if you compute the best rectangle for each bar-as-the-shortest and take the maximum, you have the answer.

For a given bar at index i with height h, the widest rectangle of height h extends:

left, until the first bar shorter than h (call the index just after it the left boundary), and
right, until the first bar shorter than h.

So the whole problem reduces to: for each bar, find the nearest shorter bar to its left and the nearest shorter bar to its right. That is two “next smaller element” queries, and the monotonic stack answers both in one pass.

The monotonic-increasing stack of indices

Keep a stack of indices whose heights are non-decreasing from bottom to top. Walk the bars left to right. The invariant: every index still on the stack is a bar that has not yet met a strictly shorter bar to its right, so its right boundary is unknown and it is still “waiting.” (Non-decreasing, not strictly increasing: because you only pop when the incoming bar is strictly shorter than the top, two bars of equal height both stay on the stack. That is fine, and the width formula below still gives the right answer for the equal case.)

When you reach bar i:

While the stack is non-empty and the current bar is shorter than the bar at the top of the stack, the bar on top has just met its nearest shorter bar to the right, which is i. So it is done waiting: pop it and compute its rectangle now.
After the popping stops, push i. (Its height is now at least the height of whatever is beneath it, preserving the non-decreasing invariant.)

Storing indices, not heights, is deliberate: the width is a distance between positions, so you need the indices, and you can always read a height back with heights[index].

The width formula, and its off-by-one

This is the step that people get wrong, so go slowly. Suppose you pop index top (its height is heights[top], the rectangle’s height). Two boundaries determine the width:

Right boundary: the current index i. Bar i is the first bar to the right that is shorter than heights[top], so the rectangle cannot include i; it ends at i - 1.
Left boundary: here is the subtlety. After popping top, look at what is now on top of the stack. Because the stack was non-decreasing, that element is the nearest bar to the left whose height is below heights[top] (everything between it and top was at least as tall as top and has already been popped). The rectangle cannot extend onto it, so the rectangle starts at stack[-1] + 1.

Therefore, after the pop:

height = heights[top]
if stack is empty:
    width = i            # nothing shorter to the left: extends from index 0 to i-1
else:
    width = i - stack[-1] - 1
area  = height * width
best  = max(best, area)

Note the two traps in one formula. The popped bar top is not the left boundary; the element beneath it is, which is why the width reads stack[-1] after the pop, not top. And when the stack empties, the rectangle reaches all the way to the left edge, so the width is the full i, not i - 0 - 1. Get either wrong and you will be off by one bar of width on some inputs but not others, which is the worst kind of bug to chase.

The sentinel-zero trick

When the main loop ends, the stack may still hold indices, the bars that never met a shorter bar to their right (a non-decreasing tail of the histogram). You could write a second loop to drain them with a right boundary of len(heights). The cleaner move, and the one to learn, is the sentinel: pretend there is one extra bar of height 0 at the very end. Since no real bar is shorter than 0, that phantom bar forces every remaining index to pop and be computed, all inside the same loop. You implement it by iterating one index past the end and treating the height there as 0 (or by appending a 0 to a copy of the input). The sentinel converts “main loop plus clean-up loop” into a single uniform loop, which is both shorter and less buggy.

Worked micro-example

Take heights = [2, 1, 5, 6, 2, 3]. The answer is 10, the rectangle of height 5 covering the two bars at indices 2 and 3. Walk it with a sentinel 0 appended, so you iterate i over heights [2, 1, 5, 6, 2, 3, 0]:

i=0, h=2: stack empty, push. Stack indices [0] (heights [2]).
i=1, h=1: top is index 0 (height 2) which is taller than 1, pop it. Stack now empty, so width = i = 1, area = 2 * 1 = 2. best=2. Push 1. Stack [1] (heights [1]).
i=2, h=5: 5 is taller than top (height 1), no pop. Push 2. Stack [1, 2] (heights [1, 5]).
i=3, h=6: taller than top (5), no pop. Push 3. Stack [1, 2, 3] (heights [1, 5, 6]).
i=4, h=2: top index 3 (height 6) > 2, pop it. After pop, top is index 2, width = 4 - 2 - 1 = 1, area = 6 * 1 = 6. best=6. Top index 2 (height 5) > 2, pop it. After pop, top is index 1, width = 4 - 1 - 1 = 2, area = 5 * 2 = 10. best=10. Top index 1 (height 1) is not > 2, stop. Push 4. Stack [1, 4] (heights [1, 2]).
i=5, h=3: taller than top (2), no pop. Push 5. Stack [1, 4, 5] (heights [1, 2, 3]).
i=6, h=0 (sentinel): pop index 5 (height 3), top is now 4, width = 6 - 4 - 1 = 1, area = 3 * 1 = 3. Pop index 4 (height 2), top is now 1, width = 6 - 1 - 1 = 4, area = 2 * 4 = 8. Pop index 1 (height 1), stack empty, width = i = 6, area = 1 * 6 = 6. Stack empty, loop ends.

Maximum area seen: 10 (the height-5 rectangle covering indices 2 and 3, found when bar i=4 popped index 2). If your code reproduces 10 on this input, your width logic and your sentinel are both correct. If you get 9 or 12, you have the off-by-one; re-check whether you used stack[-1] after the pop and whether the empty-stack case uses i.

The key insight, in one sentence

Every rectangle is capped by its shortest bar, so for each bar you ask “how wide a rectangle can this bar cap,” and a single increasing monotonic stack answers that for every bar in one pass by finding, on each pop, both the nearest shorter bar to the right (the current index) and to the left (the new stack top).

Exact complexity

Time: O(n). The outer loop visits each of the n bars (plus the one sentinel step) once. The inner while looks like it could make this quadratic, but each index is pushed exactly once and popped at most once over the entire run, so the total pop work across all iterations is at most n. Summed over the whole pass it is O(n), the amortized argument from this week’s core concepts.
Space: O(n). In the worst case (a strictly increasing histogram) every bar is still waiting on the stack at once, so the stack holds up to n indices.

Your work this week

Implement Largest Rectangle in Histogram yourself, in your own work repo (for example largest-rectangle.py). Use an increasing monotonic stack of indices, compute the area on each pop with the width formula above, and use the sentinel-zero to flush. Do not copy a solution; build it from the reframe and the formula.
Run it on the worked example [2, 1, 5, 6, 2, 3] (expect 10) and on the edge cases: a single bar [4] (expect 4), a strictly increasing histogram like [1, 2, 3, 4, 5] (expect 9, the 3 * 3 rectangle over the top three… verify it yourself), and a flat histogram [3, 3, 3] (expect 9). Then submit to LeetCode’s judge.
In your debrief, state the exact complexity above and, in your own words, the amortized argument for why the single inner while does not make the pass O(n^2). Also write down the two off-by-one traps (the left boundary is stack[-1] after the pop, not the popped index; the empty-stack width is i).
Commit with the five-question debrief in the message.

When you can explain, from memory and with no AI open, why the popped bar (not the trigger) is the one you finalize, why the width uses the stack top after the pop, and why the whole thing is O(n), you own this problem. That explanation is exactly what an interviewer will ask for, and the monotonic stack you built here is the same one that solves Daily Temperatures and every other “next greater / next smaller” problem.