LeetCode #84 Hard

Largest Rectangle in Histogram

Given bar heights, find the largest rectangle that fits under the histogram.

stackmonotonic-stack

02

Intuition

💡

The best rectangle using bar i as its height extends to the nearest shorter bar on each side. A monotonic increasing stack finds both boundaries in one pass: when a bar pops, the popper is its right boundary and the new stack top its left.

03

Approach

1

Every rectangle is pinned by a bar

The optimal rectangle's height equals some bar's full height — so compute, for each bar, its widest reach.

2

Pop = settle

Keep indices of increasing heights. When h[i] < top, the top pops: its width is i − (new top) − 1, area = height × width. Settle all taller bars.

3

Sentinel flush

Append a 0-height bar to force every index to settle by the end. Each bar pushes and pops once → O(n).

04

Solution & live demo

python

▶1class Solution:
▶2    def largestRectangleArea(self, heights):
▶3        stack, best = [], 0
▶4        for i, h in enumerate(heights + [0]):     # sentinel flush
▶5            while stack and heights[stack[-1]] > h:
▶6                height = heights[stack.pop()]
▶7                left = stack[-1] if stack else -1
▶8                best = max(best, height * (i - left - 1))
▶9            stack.append(i)
▶10        return best

05

Edge cases

Increasing histogram

Nothing settles until the sentinel; widths then span from each bar to the end.

Empty stack after a pop

Left boundary is −1 → width is the full prefix, handled by the ternary.

06

Complexity

Time

O(n)

Space

O(n)

One push and one pop per bar.