Largest Rectangle in Histogram
Given an array heights
Example 1
Output: 10
Explanation: the bars of height 5 and 6 together hold a rectangle of height 5 and width 2.
Example 2
Output: 4
How to Think About It
Step 1: Fix the height
The best rectangle's height equals one of the bars: the shortest bar it covers. So for each bar i, ask: how wide can a rectangle of exactly heights[i]
area(i) = heights[i] × (nextSmaller - previousSmaller - 1)
Checking that for every bar by scanning is O(n²).
Step 2: When does a bar's rectangle end?
Read bars left to right. While heights go up, every earlier bar's rectangle can still grow to the right:
When a shorter bar arrives, every taller bar before it is blocked. Their rectangles are finished, and we can compute them now:
The short bar's own rectangle is not blocked by the taller bars: it extends left underneath them.
Step 3: A stack of bars with increasing heights
Keep a stack of bar indices whose rectangles are still open; their heights increase from bottom to top. For each new bar i:
- while the top bar is taller than bar i, pop it. Bar i is its next smaller bar, and the new top of the stack is its previous smaller bar (or -1 if the stack is empty). Its width is
;i - newTop - 1 - push i.
Step 4: Flush at the end
Bars still on the stack at the end never met a shorter bar on the right. Processing an extra bar of height 0 at position n pops and measures all of them.
Walkthrough
heights = [2, 1, 5, 6, 2, 3]
| i | Height | Popped bar (height) | Width | Area | Stack after |
|---|---|---|---|---|---|
| 0 | 2 | [0] | |||
| 1 | 1 | 0 (2) | 1 - (-1) - 1 = 1 | 2 | [1] |
| 2 | 5 | [1, 2] | |||
| 3 | 6 | [1, 2, 3] | |||
| 4 | 2 | 3 (6), then 2 (5) | 1, then 4 - 1 - 1 = 2 | 6, then 10 | [1, 4] |
| 5 | 3 | [1, 4, 5] | |||
| 6 | 0 | 5 (3), 4 (2), 1 (1) | 1, 4, 6 | 3, 8, 6 | [6] |
The largest area is 10.
Java Solution
The loop runs to i == n
import java.util.ArrayDeque;
import java.util.Deque;
public class LargestRectangleInHistogram {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
Deque<Integer> stack = new ArrayDeque<>(); // indices with increasing heights
int best = 0;
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i]; // a final bar of height 0 empties the stack
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int left = stack.isEmpty() ? -1 : stack.peek(); // first shorter bar on the left
int width = i - left - 1; // i is the first shorter bar on the right
best = Math.max(best, height * width);
}
stack.push(i);
}
return best;
}
}
The original implementation,
Complexity
- Time: O(n): each bar is pushed and popped once.
- Space: O(n) for the stack.
Running this on each row of a 0/1 matrix, with heights counting the 1s above, solves