Find the largest rectangle that fits under histogram bars.
Start with the concrete trace below. It shows the state the algorithm must carry as it runs.
Problem trace
Largest Rectangle in Histogram: Keep increasing (start,height) candidates; the first shorter bar closes each taller candidate at its exact maximal width.
Input and goalFind the largest rectangle that fits under histogram bars.
Initialize the increasing stackStart with an empty stack, best = 0, and scan the real histogram before an appended zero sentinel.
Push height 2Nothing taller is waiting, so push (start 0, height 2).
Height 1 closes height 2At index 1, 2 > 1, so pop (0,2): area = 2 * (1 - 0) = 2. Carry start = 0 for the shorter bar.
Push height 1 from carried startPush (0,1), preserving that height 1 can extend back through index 0.
Push height 5At index 2, 5 is above stack top 1, so push (2,5).
Push height 6At index 3, 6 is above stack top 5, so push (3,6).
Height 2 closes height 6At index 4, pop (3,6): 6 cannot cross the shorter height 2, so area = 6 * (4 - 3) = 6 and start becomes 3.
The same bar closes height 5Stack top 5 is still taller than 2, so pop (2,5): area = 5 * (4 - 2) = 10. Carry start back to 2.
Push height 2 from index 2Push (2,2), because the popped bars prove height 2 extends left to index 2.
Push height 3At index 5, 3 is above stack top 2, so push (5,3).
Sentinel closes height 3The appended 0 at index 6 is shorter than 3, so pop (5,3): area = 3 * (6 - 5) = 3.
Sentinel closes height 2Pop (2,2): height 2 spans indices 2 through 5, so area = 2 * (6 - 2) = 8.
Sentinel closes height 1Pop (0,1): height 1 spans the full histogram, so area = 1 * (6 - 0) = 6. No candidate remains unresolved.
Push the sentinelAfter the pop loop, the implementation pushes (0,0). It contributes no area but leaves the loop transition fully represented.
Return the largest closed areaEvery bar has now met its first shorter right boundary. The largest recorded rectangle has height 5, width 2, and area 10.
- Recognize it
- Use it when each element needs the widest contiguous span for which it remains the limiting minimum, and the first smaller boundary finalizes that span.
- Keep true
- Stack heights are nondecreasing; each pair (start,height) can extend from start through index-1, and every popped height receives index as its first smaller right boundary while propagating its start to the incoming shorter bar.
- Reuse it
- When the first violating element determines an unresolved candidate’s right boundary, keep candidates monotone and finalize them in reverse order; propagate the oldest valid start across every pop.
Pattern: Increasing stack.
Simple idea: Save increasing heights and where each height began. A shorter bar ends the range of every taller saved bar. Calculate those areas when they end.
def largest_rectangle_area(heights: list[int]) -> int:
stack: list[tuple[int, int]] = []
best = 0
for index, height in enumerate(heights + [0]):
start = index
while stack and stack[-1][1] > height:
start, old_height = stack.pop()
best = max(best, old_height * (index - start))
stack.append((start, height))
return bestCost: time and space.