Largest Rectangle in Histogram · Compound Engineer

Monotonic stack · Nearest shorter bar

Hard · O(n) time · O(n) space

Problem

You are given an array heights. Each value is the height of one bar in a bar chart. Every bar is 1 wide and the bars touch. Return the area of the largest rectangle that fits inside the chart. The rectangle sits on the bottom line and covers whole bars.

Example 1 Input: heights = [2, 1, 5, 6, 2, 3] Output: 10 (bars 2 and 3 are both at least 5 tall: 5 × 2) Example 2 Input: heights = [2, 4] Output: 4 (bar 1 alone: 4 × 1)

Constraints 1 ≤ heights.length ≤ 10^5 0 ≤ heights[i] ≤ 10^4

What the problem asks for

A rectangle covers a run of neighbouring bars.
Its height is the shortest bar in the run. Anything taller would stick out.
Its area is that height times the number of bars. We want the largest.

Start with the direct approach

Every rectangle has a shortest bar that sets its height. So try each bar i as that bar and make the rectangle as wide as it can be:

Walk left from i while the bars are at least as tall. That gives left.
Walk right the same way. That gives right.
Area = heights[i] × (right − left + 1). Keep the largest.

The code

Time and space

Time: O(n²). Each of the n bars can walk across up to n bars. On a rising chart such as [1, 2, …, n] the total is about n²/2, which is 5 × 10⁹ for n = 10⁵. Space: O(1).

Building the faster solution

The area is one multiplication. All the time goes into one question per bar: where does its rectangle stop on the left and on the right? We answer it in four steps.

Each bar's rectangle is fixed by two edges

The rectangle of bar i (height h) stops at the first shorter bar on each side. Call their positions the left edge (−1 if there is none) and the right edge (n if there is none). Everything between them is at least h tall, so the width is right − left − 1. For bar 2 below: 4 − 1 − 1 = 2.

Bar	Height	Left edge	Right edge	Width	Area
0	2	−1	1	1	2
1	1	−1	6	6	6
2	5	1	4	2	10
3	6	2	4	1	6
4	2	1	6	4	8
5	3	4	6	1	3

Read left to right and find the right edges

Bars we have read that have no right edge yet are waiting bars. When a new bar arrives, every waiting bar taller than it has found its right edge: the new bar. The others keep waiting, and the new bar starts waiting too.

The waiting bars form a stack

From oldest to newest, the waiting bars are never getting shorter. A shorter bar after a waiting bar would have ended it. So the bars a new bar ends are the newest ones: take the newest, and if it is taller, end it and look at the next. We stop at the first one that is not taller. Adding and taking only at the end makes it a stack.

The left edge is the bar below it in the stack

When bar j ends bar i, take i out. The bar now on top, k, is the left edge of i, or −1 if the stack is empty.

Why: k is not taller than i. Suppose a bar between k and i were shorter than i. The shortest of those (the last one, if several) was never ended, so it would still be on the stack between k and i. But k is directly below i. So every bar between them is at least as tall as i.

If k is equal in height to i, the rectangle of i could reach further left, but we do not need it to. k is ended by the same j and measures that full width itself.

The end of the chart

Bars never ended by a shorter bar have right edge n. Add one extra bar of height 0 at the end. It ends all of them, and its own area is 0.

The solution

Prerequisite

This uses a monotonic stack: a stack that keeps its values in order. New to it? Read Monotonic Stack first.

Go through the bars, then one extra bar of height 0. The stack holds positions of waiting bars.
top bar is taller than bar j⟶take it out as i, left = new top (or −1), area = heights[i] × (j − left − 1) and repeat.
otherwise⟶add j to the stack
Return the largest area.

Pick an input and press Play, or use the arrow keys.

Equal bars

A bar is taken out only when the top is strictly taller, so equal bars wait side by side. On [3, 3, 3] the extra bar measures widths 1, 2 and then 3. The oldest bar gets the full width, and the answer is 9.

Why it works

Every candidate is measured. The best rectangle has a shortest bar, and its rectangle fits inside the widest one of that height. Every bar is added once, and the extra bar ends the rest, so every bar is measured once.
The right edge is correct. A bar stays on the stack until a shorter bar arrives, so j is the first shorter bar after i.
No area is too large. Every bar between k and j is at least as tall as i, so each rectangle we measure really exists.

Complexity

O(n)

Time. Here's why: each position is added once and taken out at most once, so the inner while loop runs at most n times in total. One bar can take out many, which makes this an amortized bound, but the total is at most about 2n stack operations.

O(n)

Space. The stack holds every bar on a chart that only rises, such as [1, 2, 3, 4, 5].

What can be optimized

Time is already optimal. Every bar can change the answer, so all n must be read.
Space is O(n) only in the worst case, a long rising stretch. Charts with dips keep the stack short.
For a 0/1 grid, reuse the same stack for each row: O(columns) extra space.

Check your understanding

Checkpoint 1 · Predict: the stack is [1, 4, 5] on [2, 1, 5, 6, 2, 3, …]. A bar of height 2 arrives at position 6. What happens?

AnswerBar 5 (height 3) is taller, so it is taken out: left = 4, width 1, area 3. The next top, bar 4 (height 2), is not taller, so we stop and add bar 6. Stack [1, 4, 6].

Checkpoint 2 · Why not measure a bar's rectangle when we add it?

AnswerIts right edge is not known yet. Bar 2 (height 5) would look like width 1, but bar 3 is taller, so the rectangle grows to width 2. We must wait for a shorter bar.

Checkpoint 3 · What is the answer for [4, 2, 4], and which bar is taken out last?

Answer6. Bar 1 (height 2) takes out bar 0 (area 4). The extra bar then takes out bar 2 (area 4) and bar 1 (left = −1, width 3, area 6). The shortest bar goes last because it spans the whole chart.

Interviewer follow-ups

Open one to see an answer you could say out loud.

"Now the input is a grid of 0s and 1s. Find the largest rectangle of 1s."

What they are checkingWhether you reuse a solved problem. This is the most common follow-up.

A strong answerTreat each row as the bottom of a histogram: a column's height is the number of 1s going up from that row, reset to 0 at a 0. Run this solution once per row: O(rows × columns) time, O(columns) space. See Maximal Rectangle.

"What changes if the bars have different widths?"

What they are checkingWhether you know where the width comes from.

A strong answerOnly the width formula. The edges are the same bars. Keep prefix sums of the widths, so the width between the edges is start[j] − start[left + 1] instead of j − left − 1. Still O(n).

"Would it still work if you take a bar out when the top is taller or equal?"

What they are checkingWhether you understand the equal-bar case.

A strong answerYes. An equal bar then ends the older one, which measures a narrower width, but the newer equal bar keeps the same left edge and later measures the full width. The widest rectangle of every height is still measured once.

Spot this pattern

Each element's answer depends on the nearest smaller (or larger) element on one or both sides.
A brute force where every element walks until it meets something.
"Largest area", "span", "next greater element", "days until warmer".

When it does not apply: if the stopping rule is not "first smaller or larger" (for example "the nearest bar at least 3 taller"), the waiting bars are not in order and a plain stack is not enough.