On this page
Description
Bars of width 1 stand side by side; what's the largest rectangle that fits under them? Trying every pair of edges is O(n^2). Every candidate rectangle, though, is as tall as its shortest bar - so for each bar, you only need the widest stretch around it where it is the shortest: from the nearest shorter bar on its left to the nearest shorter bar on its right.
This skill covers finding each bar's nearest shorter neighbors with one increasing stack, measuring its rectangle when it's popped, and flushing the stack with a final zero-height bar. It also covers turning a binary matrix into one histogram per row.
We'll go from simple to more technical:
- The pattern: Largest Rectangle in Histogram with an increasing stack of indices.
- A second flavor: Maximal Rectangle, a matrix of 1s as stacked histograms.
- Where it shows up (free space in occupancy grids, layout, image masks).
- What breaks it: no final flush, the width formula, overflow, the matrix reset.
The approach
Java
int largestRectangleArea(int[] heights) {
int n = heights.length, best = 0;
Deque<Integer> stack = new ArrayDeque<>(); // indices, heights increasing bottom to top
for (int i = 0; i <= n; i++) {
int cur = (i == n) ? 0 : heights[i]; // a final 0 flushes every remaining bar
while (!stack.isEmpty() && heights[stack.peek()] >= cur) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1; // between the two shorter bars
best = Math.max(best, height * width);
}
stack.push(i);
}
return best;
}
Python
def largest_rectangle_area(heights: list[int]) -> int:
n, best = len(heights), 0
stack = [] # indices, heights increasing bottom to top
for i in range(n + 1):
cur = 0 if i == n else heights[i] # a final 0 flushes every remaining bar
while stack and heights[stack[-1]] >= cur:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1 # between the two shorter bars
best = max(best, height * width)
stack.append(i)
return best
When bar i is shorter than the top of the stack, the popped bar has found its right boundary (i); its left boundary is the bar now exposed on the stack (or the array's start if the stack is empty). Its rectangle is height x (i - left - 1). The imaginary bar of height 0 at position n pops everything still waiting - without it, an increasing histogram such as [1, 2, 3, 4, 5] never pops and returns 0 instead of 9. Heights up to 10^4 and n up to 10^5 keep areas within an int; with heights up to 10^9, compute in long (Python's ints don't overflow).
A second flavor: a matrix of 1s as stacked histograms
The largest rectangle of 1s in a binary matrix: for each row, let heights[j] be the number of consecutive 1s ending at that row in column j - reset to 0 at a 0. Each row is then a histogram, and the answer is the best histogram area over all rows:
Java
int maximalRectangle(int[][] grid) {
int[] heights = new int[grid[0].length];
int best = 0;
for (int[] row : grid) {
for (int j = 0; j < row.length; j++) heights[j] = row[j] == 1 ? heights[j] + 1 : 0;
best = Math.max(best, largestRectangleArea(heights));
}
return best;
}
Python
def maximal_rectangle(grid: list[list[int]]) -> int:
heights = [0] * len(grid[0])
best = 0
for row in grid:
heights = [h + 1 if cell == 1 else 0 for h, cell in zip(heights, row)]
best = max(best, largest_rectangle_area(heights))
return best
That's O(rows x cols). Forgetting the reset (keeping the old height at a 0) builds towers over gaps and overstates the area.
Where you'll see it
Finding the largest free rectangle in an occupancy grid (placing a window or widget on a screen, floor-plan layout, finding empty regions in an image mask) is the matrix version. Profile "skylines" in computational geometry use the same nearest-shorter-bar boundaries.
Which tool for which job?
| You need | Use |
|---|---|
| The largest rectangle under a histogram | an increasing stack, popped by shorter bars |
| The largest rectangle of 1s in a matrix | per-row heights, then the histogram answer |
| The largest square of 1s | a DP: min of up, left and diagonal, plus 1 |
| The number of all-1 rectangles | per-row heights and a stack of running counts |
| Water trapped between bars | a stack of layers, or two pointers |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| No final height-0 bar | [1, 2, 3, 4, 5] returns 0 instead of 9 | flush with a 0 at index n |
| Width from the popped index | rectangles come out too narrow | i - newTop - 1, or i when the stack is empty |
| height x width in an int | 100,000 bars of 10^9 gave 2147447808 | multiply in long |
| No reset at a 0 cell | towers over gaps overstate the area | heights[j] = 0 at a 0 |
| Expanding from every bar | 49,995,000 steps for 10,000 sorted bars | the stack, O(n) |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. When a bar is popped, what are its left and right boundaries?
Show answer
Right: the current index i, the first bar to its right that is shorter. Left: the bar now on top of the stack (the nearest shorter bar to its left), or -1 (the start) if the stack is empty. Its width is the gap between them: i - left - 1.
2. What goes wrong without the height-0 bar at the end?
Show answer
Bars that never meet a shorter bar to their right are never popped, so their rectangles are never measured. For [1, 2, 3, 4, 5] nothing is ever popped and the answer comes out 0 instead of 9.
3. How does a binary matrix become histograms?
Show answer
For each row, column j's height is the number of consecutive 1s ending at that row (reset to 0 at a 0). Every all-1s rectangle has its bottom edge on some row, where it's a rectangle under that row's histogram.
Key takeaways
- For each bar, the best rectangle spans from the nearest shorter bar on the left to the nearest shorter on the right.
- Pop when the current bar is shorter; width = i - newTop - 1 (or i if the stack is empty).
- Append a height-0 bar to flush the stack.
- Binary matrix: per-row heights of consecutive 1s, then the histogram answer per row.