Largest Rectangle in Histogram

Given heights, the heights of adjacent bars each of width 1 in a histogram, return the area of the largest rectangle that fits entirely inside the histogram.

Hints

· Stuck? Reveal one nudge at a time.

For each bar, how far can a rectangle of that height extend before a shorter bar stops it?

That range is between the previous smaller and next smaller bars.

An increasing monotonic stack finds both boundaries; measure a bar's rectangle when a shorter bar pops it.

Common doubts

It ensures that when a shorter bar arrives, every taller bar on top has just met its next-smaller boundary, so its rectangle can be finalized right then.

The rectangle spans from just after the new stack top (previous smaller) to just before i (next smaller): width = i - newTop - 1, or i if the stack is empty.

It's shorter than every bar, so it forces the stack to flush and measure all remaining bars at the end.

Interview follow-ups

· What an interviewer asks next.

Build a histogram of consecutive 1s ending at each row of a binary matrix, and run this algorithm on each row's histogram.

Yes — after the loop, keep popping remaining bars using n as the right boundary; the sentinel just folds that into the main loop.

Fun facts

This is the canonical monotonic-stack 'rectangle' problem — Maximal Rectangle, Trapping Rain Water (stack variant), and more reduce to it.
The previous/next-smaller boundaries here are exactly the spans used in Sum of Subarray Minimums.

Asked at

AmazonGoogleMicrosoftMeta

Frequently Sometimes Occasionally

Example 1

Input: heights = [2,1,5,6,2,3]
Output: 10
The rectangle over the bars of height 5 and 6 has width 2 and area 10.

Example 2

Input: heights = [2,4]
Output: 4
The bar of height 4 alone (area 4) beats both bars at height 2 (area 4 as well).

Constraints

- 1 <= heights.length <= 10^5 - 0 <= heights[i] <= 10^4

Each bar can be the height of a rectangle that extends left and right as far as no shorter bar blocks it. So the widest rectangle of height heights[i] reaches from just after the previous smaller bar to just before the next smaller bar. A single monotonic increasing stack finds those boundaries and the answer in O(n).

Prerequisites

Before you start

· Concepts used directly in the solution.

Previous/next smaller. The boundaries that cap how far a bar's rectangle can extend.

Monotonic stack. An index stack of increasing heights; a shorter incoming bar triggers area computations.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rectangle

“Must the rectangle be axis-aligned and contiguous?”

Yes — it spans a contiguous range of bars and its height is the shortest bar in that range.

“Can bars have height 0?”

Yes; such a bar contributes a zero-height (zero-area) rectangle.

The ideal opening — say it like this

For each bar, the tallest rectangle using it as the height extends until a shorter bar on either side.

I keep an increasing stack of indices; when a shorter bar arrives, I pop and compute that bar's rectangle.

The width comes from the current index and the new stack top — the previous smaller bar.

Understand the problem

Worked example — heights = [2, 1, 5, 6, 2, 3]

the tallest rectangle is heights 5 and 6 over width 2 -> area 10
answer: 10

Key observations

1Aha

A bar's rectangle is bounded by smaller neighbors

Bar i's widest rectangle at height heights[i] runs from just after the previous strictly-smaller bar to just before the next strictly-smaller bar.

2Aha

Pop when a shorter bar arrives

The incoming shorter bar is the next-smaller boundary for everything taller on the stack, so pop and measure those rectangles then.

3Aha

Width from the new stack top

After popping, the new top is the popped bar's previous-smaller boundary, so width = i - newTop - 1 (or i if the stack is empty).

Brute force vs optimal

	Expand each bar	Monotonic stack
Idea	For each bar, extend left/right while >= its height	Increasing index stack; measure on a shorter bar
Time	O(n^2)	O(n)
Space	O(1)	O(n)

Full code is in the Approaches selector below.

Summary

Key takeaway

Each bar's widest rectangle runs between its previous- and next-smaller bars. An increasing index stack finds those on the fly: pop when a shorter bar arrives, take height x (i - newTop - 1), and use a trailing 0 to flush. O(n) time.

stack = []; best = 0
for i in 0 .. n (heights[n] = 0 sentinel):
    while stack and heights[stack.top] > heights[i]:
        h = heights[stack.pop]
        w = stack ? i - stack.top - 1 : i
        best = max(best, h * w)
    stack.push(i)
return best