27.Largest Rectangle in Histogram

HardStack · 7/7

Problem

Given an array heights where heights[i] is the height of a histogram bar of width 1, return the area of the largest rectangle that fits entirely inside the histogram.

A rectangle spans a contiguous range of bars, and its height is limited by the shortest bar in that range.

Examples

Input:  heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: Bars 5 and 6 (indices 2–3) form a rectangle of height 5 and width 2 → area 10.

Input:  heights = [2, 4]
Output: 4
Explanation: Either the single bar of height 4, or both bars at height 2 — both give area 4.

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

💡 Key Insight

The best rectangle has some bar i as its shortest bar, and then it should extend as far as possible: left until the first shorter bar, right until the first shorter bar. Its area is heights[i] * (right - left - 1). A monotonic increasing stack finds both boundaries for every bar in a single pass: when bar i is popped by a shorter bar, that shorter bar is its right boundary and the new stack top is its left boundary.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Try every range [i, j]. Extending j one bar at a time, keep the running minimum height; the rectangle for that range has area minHeight * (j - i + 1).

Algorithm

maxArea = 0.
For each i: minHeight = +infinity.
For each j >= i: minHeight = min(minHeight, heights[j]); maxArea = max(maxArea, minHeight * (j - i + 1)).
Return maxArea.

Visualization

heights = [2, 1, 5, 6, 2, 3]

i=2: [5] → 5·1=5, [5,6] → 5·2=10 ✓, [5,6,2] → 2·3=6, [5,6,2,3] → 2·4=8
i=1: [1..] → min is 1 everywhere → at most 1·5=5
best = 10

Code

java

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < n; j++) {
                minHeight = Math.min(minHeight, heights[j]); // shortest bar in [i, j]
                maxArea = Math.max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
}

Complexity

Time: O(n²) — every range is examined; too slow for n = 10^5.
Space: O(1).

Nearest Smaller Bars (Two Stack Passes)

TimeO(n)SpaceO(n)

Intuition

Fix each bar as the shortest bar of its rectangle. We need leftSmaller[i] (index of the nearest bar to the left that is shorter, or -1) and rightSmaller[i] (nearest shorter to the right, or n). Both are classic "next smaller element" queries, each solved with a monotonic stack in O(n).

Algorithm

Left pass: for i from 0 to n-1, pop while heights[top] >= heights[i]; leftSmaller[i] = empty ? -1 : top; push i.
Right pass: for i from n-1 down to 0, pop while heights[top] >= heights[i]; rightSmaller[i] = empty ? n : top; push i.
Answer = max over i of heights[i] * (rightSmaller[i] - leftSmaller[i] - 1).

Dry Run

i	height	leftSmaller	rightSmaller	width	area
0	2	-1	1	1	2
1	1	-1	6	6	6
2	5	1	4	2	10
3	6	2	4	1	6
4	2	1	6	4	8
5	3	4	6	1	3

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] leftSmaller = new int[n];
        int[] rightSmaller = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // nearest strictly shorter bar on the left
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();
        // nearest strictly shorter bar on the right
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            rightSmaller[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = rightSmaller[i] - leftSmaller[i] - 1;
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        return maxArea;
    }
}

Complexity

Time: O(n) — each pass pushes and pops every index at most once.
Space: O(n) — two boundary arrays and the stack.

One-Pass Monotonic StackOptimal

TimeO(n)SpaceO(n)

Intuition

Keep a stack of indices with increasing heights. When the current bar i is shorter than the top, the top bar cannot extend further right — i is its right boundary. After popping it, the new top is the nearest shorter bar on its left, so its width is i - newTop - 1 (or i if the stack is empty). Compute the area at pop time. A sentinel bar of height 0 at i = n flushes everything left on the stack.

Algorithm

Empty stack; maxArea = 0.
For i from 0 to n (inclusive), with h = (i == n) ? 0 : heights[i]:
- While the stack is non-empty and heights[top] >= h:
  - height = heights[pop()].
  - width = stack.isEmpty() ? i : i - stack.peek() - 1.
  - maxArea = max(maxArea, height * width).
- Push i.
Return maxArea.

Dry Run

flowchart TD
    A["i0 h2: stack [2]"] --> B["i1 h1: pop 2, width 1 → area 2<br/>stack [1]"]
    B --> C["i2 h5, i3 h6: push<br/>stack [1, 5, 6]"]
    C --> D["i4 h2: pop 6, width 4-2-1 = 1 → 6<br/>pop 5, width 4-1-1 = 2 → 10<br/>stack [1, 2]"]
    D --> E["i5 h3: push<br/>stack [1, 2, 3]"]
    E --> F["i6 sentinel h0:<br/>pop 3 → 3·1 = 3<br/>pop 2 → 2·4 = 8<br/>pop 1 → 1·6 = 6"]
    F --> G["maxArea = 10"]

(The stack stores indices; heights are shown for readability.)

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new ArrayDeque<>(); // indices, heights increasing
        int maxArea = 0;
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i]; // sentinel 0 flushes the stack at the end
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int height = heights[stack.pop()];
                // left boundary = new top (first shorter bar), right boundary = i
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

Complexity

Time: O(n) — every index is pushed once and popped once.
Space: O(n) — an increasing input keeps all indices on the stack until the sentinel.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Nearest Smaller (two passes)	O(n)	O(n)
One-Pass Monotonic Stack	O(n)	O(n)

Common Pitfalls

Computing the width as i - poppedIndex — the rectangle extends left past the popped index to just after the new stack top, so use i - stack.peek() - 1.
Forgetting to flush the stack at the end; an increasing histogram like [1, 2, 3] would never pop. The 0-height sentinel fixes this.
Mishandling the empty-stack case: when nothing shorter remains on the left, the rectangle starts at index 0, so the width is i.
Worrying about overflow: the max area is 10^4 * 10^5 = 10^9, which still fits in an int.