Example 1
ready- Input
heights = [ 2, 1, 5, 6, 2, 3 ]- Expected
10- Why
- the two middle bars form a 2 × 5 rectangle
Largest Rectangle in Histogram
50 min · largestRectangleArea()A row of bars can hide a much wider rectangle than its tallest bar suggests.
You're given heights, where each number is the height of one bar. Every bar has width
1 and rests on the same baseline. Return the largest area of an axis-aligned
rectangle — a rectangle whose sides stay horizontal and vertical — that fits entirely
inside the bars.
A few ground rules:
- A rectangle covers one or more consecutive bars.
- Its height can't exceed the shortest bar it covers.
- A height of
0creates a gap, but it remains part of the input. - The answer always fits in a signed 32-bit integer.
Constraints
1 <= heights.length <= 100_0000 <= heights[i] <= 10_000
Hints
Start with a fixed left edge
Move a right edge across the histogram while tracking the shortest bar in that span. The width and minimum height give you every rectangle for that left edge.
When does a bar learn its full width?
A bar can keep extending right while later bars are at least as tall. The first shorter bar proves that its right boundary has arrived.
Keep unfinished bars in order
Store indices whose heights increase from bottom to top. When a shorter bar arrives,
pop every bar it closes. After a pop, the new top marks the first shorter bar on the
left, so the closed bar's width is right - left - 1.
Follow-up
Can you explain why each index enters and leaves the stack at most once, even when many bars have the same height?
Visible cases
Examples
Example 2
ready- Input
heights = [ 2, 4 ]- Expected
4- Why
- either both bars at height 2 or the second bar alone gives area 4
Example 3
ready- Input
heights = [ 2, 1, 2 ]- Expected
3- Why
- height 1 stretches across all three bars
Interview signal
Asked at
AmazonGoogleMicrosoft
Expand every left edge
Fix a left edge, then move the right edge across the remaining bars. Keep the shortest
height seen in that span; its area is shortest * width.
def largest_rectangle_area(heights: list[int]) -> int:
best = 0
for left in range(len(heights)):
shortest = heights[left]
for right in range(left, len(heights)):
shortest = min(shortest, heights[right])
width = right - left + 1
best = max(best, shortest * width)
return bestThis checks every possible horizontal span and gives each span its tallest legal rectangle. Time O(n²) — there are about n²/2 spans. Space O(1).
Increasing index stack
A monotonic stack keeps its values in one ordered direction; here, the bar heights at stored indices never decrease. Those bars are still waiting to discover how far right they can extend.
When a shorter bar appears at index right, every taller bar on top is finished. After
you pop one, the new stack top is its nearest shorter bar on the left. Its rectangle
therefore runs between those two shorter bars.
def largest_rectangle_area(heights: list[int]) -> int:
stack: list[int] = []
best = 0
for right in range(len(heights) + 1):
current = 0 if right == len(heights) else heights[right]
while stack and heights[stack[-1]] > current:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
width = right - left - 1
best = max(best, height * width)
stack.append(right)
return bestThe final virtual bar of height 0 closes every positive-height bar still waiting in
the stack. Equal heights may wait together; the leftmost copy eventually receives the
widest span, so no candidate is lost.
Time O(n) — every index is pushed once and popped at most once. Space O(n) for the stack.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
10
Run: visible + custom · Submit: full suite