Largest Rectangle in Histogram

Given an array heights of bar heights in a histogram, where every bar has width 1, return the area of the largest rectangle that fits inside the histogram. This is LeetCode 84.

Histogram with bars 2, 1, 5, 6, 2, 3
Example 1
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: the bars of height 5 and 6 together hold a rectangle of height 5 and width 2.
The largest rectangle, area 10, shaded over the bars 5 and 6
Example 2
Input: heights = [2, 4]
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] be? It extends left and right until it meets a shorter bar:

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:

Bars 2 then 3: the bar of height 2 can still extend right

When a shorter bar arrives, every taller bar before it is blocked. Their rectangles are finished, and we can compute them now:

Bars 2, 1, 3: the bar 1 blocks the bar 2 from extending

The short bar's own rectangle is not blocked by the taller bars: it extends left underneath them.

Bars 2, 1, 3, 1: a rectangle of height 1 spans all four bars

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], plus a height-0 bar at index 6. The stack holds indices.

iHeightPopped bar (height)WidthAreaStack after
02[0]
110 (2)1 - (-1) - 1 = 12[1]
25[1, 2]
36[1, 2, 3]
423 (6), then 2 (5)1, then 4 - 1 - 1 = 26, then 10[1, 4]
53[1, 4, 5]
605 (3), 4 (2), 1 (1)1, 4, 63, 8, 6[6]

The largest area is 10.

Java Solution

The loop runs to i == n with height 0 so the stack is emptied without a second loop.

Java
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, LargestRectangleInHistogram.java, is on GitHub.

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 Maximal Rectangle.