Problem Statement

Largest Rectangle in Histogram

You are given an array called heights. Each number is the height of a bar in a bar chart (a histogram), and every bar is exactly 1 unit wide. Picture bars sitting side by side, like books of different heights standing on a shelf. Your job is to find the biggest rectangle you can draw using these bars. The rectangle can span across several bars, but it can only be as tall as the shortest bar it covers. Return the area (height times width) of that largest rectangle.

hardStackStackTime: O(n) · Space: O(n)

Signals to notice

largest rectangle in histogramwidth × minimum heightnext smaller element

Brute force first

For each bar, expand left and right to find the rectangle. Each bar re-scans for boundaries. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Monotonic increasing stack: for each bar, pop all taller bars (they've found their right boundary). The rectangle height is the popped bar, width extends from the new stack top to the current index. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `heights=[2,1,5,6,2,3]`

i=0 h=2: stack empty -> push (2,0). stack=[(2,0)]
i=1 h=1: pop (2,0) area=2*(1-0)=2, max=2, start=0 -> push (1,0). stack=[(1,0)]
i=2 h=5: 1<5 no pop -> push (5,2). stack=[(1,0),(5,2)]
i=3 h=6: 5<6 no pop -> push (6,3). stack=[(1,0),(5,2),(6,3)]
i=4 h=2: pop (6,3) area=6*1=6 max=6; pop (5,2) area=5*(4-2)=10 max=10, start=2 -> push (2,2). stack=[(1,0),(2,2)]
i=5 h=3: 2<3 no pop -> push (3,5). stack=[(1,0),(2,2),(3,5)]
i=6 sentinel h=0: pop (3,5)=3; pop (2,2)=2*4=8; pop (1,0)=1*6=6; max stays 10
return max=10

What must stay true

The stack holds bar indices in increasing height order. When a shorter bar arrives, all taller bars on the stack have found their right boundary — calculate their rectangles before pushing the shorter bar. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

stack = []   # holds (height, start_index), increasing heights
for i in 0..n:                      # extra step i==n uses sentinel h=0
    h = (i==n) ? 0 : heights[i]
    start = i
    while stack and stack.top.height > h:
        height, idx = stack.pop()
        maxArea = max(maxArea, height * (i - idx))
        start = idx                 # inherit popped bar's left reach
    stack.push((h, start))
return maxArea

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not processing remaining bars after the loop — bars still on the stack haven't found a right boundary, so their right boundary is the array end. The fix is usually to return to the meaning of each move, not just the steps themselves.

Stack Pattern