Largest rectangle in a bar chart
An array heights gives the heights of bars of width 1 standing side by
side. Return the area of the largest rectangle that fits entirely inside the bars.
Examples
| Input | Output | Why |
|---|---|---|
heights = [2, 1, 5, 6, 2, 3] | 10 | Height 5 across the bars 5 and 6: width 2. |
heights = [2, 4] | 4 | Either the single bar of 4, or height 2 across both. |
heights = [5, 4, 3, 2, 1] | 9 | Height 3 across the first three bars. |
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
Hints
Hint 1
The best rectangle has some shortest bar, and it stretches as far left and right as it can without meeting anything shorter. So for each bar, what are the two limits?
Hint 2
For each bar you need the nearest shorter bar on its left and on its right. That is a "nearest smaller element" question, twice.
Hint 3
Keep indices with increasing heights on a stack. When a shorter bar arrives, it is the right limit for every taller bar it pops, and the bar below each popped one on the stack is its left limit. Add a bar of height 0 at the end to flush the stack.
Dry run on [2,1,5,6,2,3]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 12heights20i1152632435stack20best0
Push bar 0 (height 2). The stack's heights rise from bottom to top.
-
Step 2 / 12heights2011i52632435stackempty0area2best2
Bar 1 (height 1) is not taller than bar 0 (height 2), so bar 0 can stretch no further right. Its left limit is the start of the array, giving width 1 and area 2.
-
Step 3 / 12heights2011i52632435stack10best2
Push bar 1 (height 1). The stack's heights rise from bottom to top.
-
Step 4 / 12heights201152i632435stack1051best2
Push bar 2 (height 5). The stack's heights rise from bottom to top.
-
Step 5 / 12heights20115263i2435stack105162best2
Push bar 3 (height 6). The stack's heights rise from bottom to top.
-
Step 6 / 12heights2011526324i35stack1051area6best6
Bar 4 (height 2) is not taller than bar 3 (height 6), so bar 3 can stretch no further right. Its left limit is just after bar 2, giving width 1 and area 6.
-
Step 7 / 12heights2011526324i35stack10area10best10
Bar 4 (height 2) is not taller than bar 2 (height 5), so bar 2 can stretch no further right. Its left limit is just after bar 1, giving width 2 and area 10.
-
Step 8 / 12heights2011526324i35stack1021best10
Push bar 4 (height 2). The stack's heights rise from bottom to top.
-
Step 9 / 12heights201152632435istack102132best10
Push bar 5 (height 3). The stack's heights rise from bottom to top.
-
Step 10 / 12heights201152632435stack1021area3best10
The end-of-array bar of height 0 is not taller than bar 5 (height 3), so bar 5 can stretch no further right. Its left limit is just after bar 4, giving width 1 and area 3.
-
Step 11 / 12heights201152632435stack10area8best10
The end-of-array bar of height 0 is not taller than bar 4 (height 2), so bar 4 can stretch no further right. Its left limit is just after bar 1, giving width 4 and area 8.
-
Step 12 / 12heights201152632435stackempty0area6best10
The end-of-array bar of height 0 is not taller than bar 1 (height 1), so bar 1 can stretch no further right. Its left limit is the start of the array, giving width 6 and area 6. Every bar has been settled; the answer is 10.
How to think about it
Every rectangle in the chart is limited by its shortest bar. So try each bar
i as that shortest bar: the rectangle has height heights[i] and extends
left and right until it meets a strictly shorter bar. Its area is
heights[i] × (right − left − 1), where left and right are the
nearest shorter bars on each side. The answer is the largest of these n areas.
Finding both limits for every bar by scanning is O(n²). A stack of indices whose
heights increase from bottom to top gives both in one pass:
- When bar
iis shorter than the top of the stack,iis the right limit of the top bar: the first shorter bar to its right. - After popping it, the new top is the left limit: every bar between them is at least as tall, or it would still be on the stack.
- So each pop settles one bar completely. Compute its area there and then.
A bar of height 0 appended at the end is shorter than everything, so it pops whatever remains and no second loop is needed.
This is the same stack as "days until a warmer day", turned upside down: there the stack held falling values waiting for a bigger one; here it holds rising values waiting for a smaller one. Recognising "nearest smaller on both sides" is most of the problem.
Complexity. Time O(n) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def largest_rectangle(heights):
stack = [] # indices; their heights rise from bottom to top
best = 0
for i, h in enumerate(heights + [0]): # the final 0 pops everything left
while stack and heights[stack[-1]] >= h:
top = stack.pop() # i is the first bar to its right that is not taller
left = stack[-1] + 1 if stack else 0 # and this is where it starts
best = max(best, heights[top] * (i - left))
stack.append(i)
return best#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& heights) {
const int n = static_cast<int>(heights.size());
std::vector<int> stack; // indices; heights rise bottom to top
long long best = 0;
for (int i = 0; i <= n; ++i) {
const int h = i == n ? 0 : heights[i]; // the final 0 pops everything
while (!stack.empty() && heights[stack.back()] >= h) {
const int top = stack.back();
stack.pop_back();
const int left = stack.empty() ? 0 : stack.back() + 1;
best = std::max(best, 1LL * heights[top] * (i - left));
}
stack.push_back(i);
}
return best;
}class Solution {
public long largestRectangle(int[] heights) {
int n = heights.length;
int[] stack = new int[n + 1]; // indices; top is stack[top - 1]
int top = 0;
long best = 0;
for (int i = 0; i <= n; i++) {
int h = i == n ? 0 : heights[i]; // the final 0 pops everything
while (top > 0 && heights[stack[top - 1]] >= h) {
int bar = stack[--top];
int left = top > 0 ? stack[top - 1] + 1 : 0;
best = Math.max(best, (long) heights[bar] * (i - left));
}
stack[top++] = i;
}
return best;
}
}function largestRectangle(heights) {
const stack = []; // indices; heights rise from bottom to top
let best = 0;
for (let i = 0; i <= heights.length; i++) {
const h = i === heights.length ? 0 : heights[i]; // the final 0 pops everything
while (stack.length && heights[stack[stack.length - 1]] >= h) {
const top = stack.pop();
const left = stack.length ? stack[stack.length - 1] + 1 : 0;
best = Math.max(best, heights[top] * (i - left));
}
stack.push(i);
}
return best;
}fn solve(heights: &[i64]) -> i64 {
let n = heights.len();
let mut stack: Vec<usize> = Vec::new(); // indices; heights rise bottom to top
let mut best = 0i64;
for i in 0..=n {
let h = if i == n { 0 } else { heights[i] }; // the final 0 pops everything
while let Some(&top) = stack.last() {
if heights[top] < h {
break;
}
stack.pop();
let left = stack.last().map_or(0, |&j| j + 1);
best = best.max(heights[top] * (i - left) as i64);
}
stack.push(i);
}
best
}import Data.Array
solve :: [Int] -> Int
solve hs = go 0 [] 0
where
n = length hs
arr = listArray (0, n - 1) hs
height i = if i == n then 0 else arr ! i -- a bar of height 0 at the end
-- the stack is a list of indices, top at the head, heights rising towards the head
go i stack best
| i > n = best
| otherwise = case stack of
(top : rest) | arr ! top >= height i ->
let left = case rest of
(j : _) -> j + 1
[] -> 0
in go i rest (max best (arr ! top * (i - left)))
_ -> go (i + 1) (i : stack) bestWhere people lose marks
- Computing the width as
i − top. The rectangle for the popped bar starts just after the bar now below it on the stack, not at the popped bar itself, because every bar in between was taller. - Forgetting the bars still on the stack at the end. Without the sentinel of height 0, the rising run [1, 2, 3, 4, 5] never pops anything and the answer 9 is missed.
- Using an empty stack as a left limit of 0 but writing the width as
i − left − 1. With no bar on the left the rectangle starts at index 0, so the width isi. - Overflow in languages with 32-bit ints if the limits are larger than these: the area can reach height × n. Use 64-bit arithmetic when in doubt.
Variants to try
- Maximal rectangle of 1s in a binary matrix: build a histogram for each row (the run of 1s above each cell) and run this algorithm on every row, O(rows × cols).
- Return the rectangle, not just its area: record the left and right limits when the best area is found.
- Two passes instead of one: compute nearest-smaller-left and nearest-smaller-right arrays separately. Longer, but easier to get right under pressure.
- Trapping rain water: another bar-chart problem, but it wants the nearest larger bars, and two pointers also solve it in O(1) space.
Next problems
Balanced brackets
Every closing bracket must match the most recent unmatched opener. "Most recent" is what a stack gives you.
Open the problem → Medium15 minDays until a warmer day
For each day, how long until it is warmer? Days wait on a stack until a warmer one arrives and settles them.
Open the problem →Write a solution and run it against the real test table.
Keep going
Balanced brackets
Every closing bracket must match the most recent unmatched opener. "Most recent" is what a stack gives you.
Open the problem → Medium15 minDays until a warmer day
For each day, how long until it is warmer? Days wait on a stack until a warmer one arrives and settles them.
Open the problem → StackThe pattern behind it
Keep the elements whose question is still open; each new element settles the ones it beats and waits its turn.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.