DSA interview question

Largest Rectangle in a Histogram

Hard · Data structures · Topics: stack, monotonic stack, array

The problem

A billboard company looks at a skyline as a histogram of building heights, each building 1 unit wide, and wants the largest rectangular banner that fits entirely against the buildings: a rectangle standing on the ground and never poking above any building it spans. For each bar, the widest rectangle of exactly that bar's height extends until the nearest shorter bar on each side. A monotonic increasing stack finds both boundaries as bars are popped: when a shorter bar arrives, it's the right boundary for everything taller on the stack, and the element below each popped bar is its left boundary.

Example: [2, 1, 5, 6, 2, 3] → 10 (the bars 5 and 6, height 5, width 2).

Function signature

long long largestRectangleArea(const vector<int>& heights);

Test cases

Input	Output	Explanation
`[2, 1, 5, 6, 2, 3]`	`10`	5 × 2
`[2, 4]`	`4`
`[6, 2, 5, 4, 5, 1, 6]`	`12`	4 × 3
`[1, 1, 1, 1]`	`4`	Equal heights span the whole width
`[3]`	`3`
`[0]`	`0`

(Confirm: heights are non-negative; each bar has width 1; the rectangle must be axis-aligned and rest on the ground.)

How interviewers phrase it

"Given an array of bar heights where each bar has width 1, return the area of the largest rectangle in the histogram" (LeetCode 84).

Clarifying questions to ask

Is every bar width 1? (Yes.)
Can heights be 0? (Yes.)
How large can the area be? (10⁵ × 10⁴ fits in 32 bits, but 64-bit is safer.)

Follow-ups to expect

"What's the brute force?"
"What are the boundaries of a bar's best rectangle?"
"How does one stack pass find both?"
"Why add a 0-height bar at the end?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview