Largest Rectangle in Histogram

This is the hardest problem in the stack section and a favourite at companies that ask hard questions. The brute force is easy. The stack solution is short but dense: one pop does three things at once, and the width formula is where most attempts break.

It is also the engine inside other problems — Maximal Rectangle in a 0/1 grid runs it once per row — so understanding it pays twice.

The problem

You are given a list of non-negative integers: the heights of bars in a histogram, each bar one unit wide, standing side by side. Return the area of the largest rectangle that fits entirely inside the histogram.

• [2, 4, 5, 3, 1, 3] → 9. Bars 1, 2 and 3 (heights 4, 5, 3) all reach height 3, so a rectangle 3 wide and 3 high fits: area 9.
• [2, 1, 5, 6, 2, 3] → 10. The bars of height 5 and 6 give 5 high and 2 wide.

Constraints: 1 ≤ n ≤ 10⁵, heights between 0 and 10⁴.

Clarifying questions

• Is every bar one unit wide? Yes.
• Can a height be 0? Yes; a rectangle cannot cross it.
• Must the rectangle sit on the base line? Yes; any rectangle inside the histogram can be pushed down to the base without getting smaller.
• Area or position? Just the area.

Approach 1: the simple way

Try every left edge. Extend to the right one bar at a time, keeping the lowest bar seen so far. The rectangle from left to right can be as tall as that lowest bar.

1def largest_rectangle_brute(heights: list[int]) -> int:2    """Try every left edge, extend right, track the lowest bar: O(n^2)."""3    best = 04    for left in range(len(heights)):5        lowest = heights[left]6        for right in range(left, len(heights)):7            lowest = min(lowest, heights[right])8            best = max(best, lowest * (right - left + 1))9    return best

Time: O(n²). Space: O(1).

At n = 10⁵ that is 5 × 10⁹ steps. It also does no pruning: even after a bar of height 0 makes every wider rectangle worthless, it keeps extending.

The key insight

Every rectangle in the answer has a shortest bar inside it, and its height equals that bar's height (otherwise it could be taller). So look at it from each bar's point of view: what is the widest rectangle whose height is exactly this bar's height?

It stretches left until the first shorter bar on the left, and right until the first shorter bar on the right. It cannot cross a shorter bar, and nothing stops it before one. So for bar i:

area(i) = heights[i] × (next_smaller(i) - previous_smaller(i) - 1)

The answer is the largest of these n areas. "Next smaller" and "previous smaller" are both monotonic-stack questions, and one increasing stack answers both at once:

• Keep indices on the stack with heights increasing from bottom to top.
• When bar i arrives and is shorter than the top bar, the top bar has just met its next smaller bar: bar i. Pop it.
• After popping, the new top is the nearest bar to its left that is shorter than it (or equal — see the edge cases). That is its previous smaller. If the stack is empty, nothing on the left is shorter, and the wall is at -1.

So at the moment a bar is popped, you know both walls, and you can compute its rectangle.

The width comes from the walls. The rectangle covers positions left_wall + 1 through i - 1. Counting them: (i - 1) - (left_wall + 1) + 1 = i - left_wall - 1. Check it: with left_wall = 1 and i = 4, the rectangle covers positions 2 and 3, two units, and 4 - 1 - 1 = 2.

Finally, bars still on the stack at the end never met a shorter bar on the right; their rectangles run to the end of the list. Appending a bar of height 0 — a sentinel — makes every remaining bar pop and be measured, with no second loop.

Approach 2: one increasing stack with a sentinel

1def largest_rectangle(heights: list[int]) -> int:2    """Area of the largest rectangle inside the histogram."""3    stack: list[int] = []                        # indices; heights increase upward4    best = 05    for i, height in enumerate(heights + [0]):   # the 0 sentinel flushes the stack at the end6        while stack and heights[stack[-1]] > height:7            bar = heights[stack.pop()]           # this bar can extend no further right8            left_wall = stack[-1] if stack else -1   # nearest shorter bar on the left9            width = i - left_wall - 110            best = max(best, bar * width)11        stack.append(i)12    return best

heights[stack[-1]] reads the original list, which is safe: the sentinel's index, n, is only ever appended after the last comparison.

Dry run on [2, 4, 5, 3, 1, 3]:

At i = 4, the bar of height 3 at index 3 is popped. The new top is index 0 (height 2), so the rectangle of height 3 covers positions 1 to 3: width 4 - 0 - 1 = 3, area 9. That is the answer. At the sentinel, the bar of height 1 has an empty stack below it, so its wall is -1 and it spans the whole list: 1 × 6.

Time: O(n) — each index pushed once and popped at most once. Space: O(n) — a rising histogram keeps every bar on the stack until the sentinel. Checked against the brute force on 500 random histograms.

Edge cases

• Rising heights, like [1, 2, 3]: nothing pops until the sentinel, which then measures all three. Without the sentinel the answer would be 0.
• Equal heights, like [3, 3, 3]: with >, equal bars stay on the stack. The sentinel pops them right to left; the last one popped has an empty stack beneath it, wall -1, width 3: area 9. The earlier, narrower measurements of the same height do no harm, because the widest one is also measured.
• Zeros: a 0 pops everything, and its own rectangle has area 0.
• One bar: the sentinel pops it: height × 1.

Follow-ups

• "Largest rectangle of 1s in a 0/1 grid" (Maximal Rectangle). Build a histogram per row — the height at each column is the number of consecutive 1s ending in this row — and run this function on each row: O(rows × cols).
• "Sum of the minimums of all subarrays." The same previous-smaller and next-smaller walls: each value is the minimum of (i - left) × (right - i) subarrays. Watch ties: use > on one side and >= on the other so equal values are not counted twice.
• "Trapping rain water with a stack." A decreasing stack; each pop fills the water above the popped bar between its two walls.