Problem 9.8 · Stack and Monotonic StackHard

Largest Rectangle in Histogram

What it teaches: For each bar, the widest rectangle at its height spans to the nearest shorter bar on each side, found with an increasing stack.

Practise it on judges as “Largest Rectangle in Histogram”.

The problem

Given bar heights of width 1, return the area of the largest rectangle that fits inside the histogram.

Example 1

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10

Bars 5 and 6, height 5 × width 2.

Example 2

Input: heights = [2, 4]
Output: 4

Constraints

1 ≤ n ≤ 10⁵
0 ≤ height ≤ 10⁴

Pattern clues in the wording

→ For each bar: how far left and right can it extend at its own height?
→ "Nearest smaller on each side" → monotonic stack

These clues point to Monotonic Stack: Keep a stack whose values only increase (or decrease); each element pops everything it beats, finding "next greater/smaller" in one pass.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	heights = [2,1,5,6,2,3]	10
2	heights = [2,4]	4

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Brute force: expand from every bar · O(n²)2. Optimal: increasing stack · O(n)

Brute force: expand from every bar

Time O(n²) Space O(1)

For each bar, extend left and right while bars are at least as tall.

Approach 1

class Solution {
    public int largestRectangleArea(int[] h) {
        int best = 0;
        for (int i = 0; i < h.length; i++) {
            int l = i, r = i;
            while (l > 0 && h[l - 1] >= h[i]) l--;
            while (r < h.length - 1 && h[r + 1] >= h[i]) r++;
            best = Math.max(best, h[i] * (r - l + 1));
        }
        return best;
    }
}

Verdict: Too slow for 10⁵ equal bars.

Optimal: increasing stack

Time O(n) Space O(n)

Keep indexes with increasing heights. When bar i is shorter than the top, pop the top t: bar i is the first shorter bar on its right, and the new top (after popping) is the first shorter bar on its left. Its rectangle is h[t] × (i − newTop − 1). A sentinel height 0 at the end flushes the stack.

▶ Dry run: Popping gives both boundariesheights = [2, 1, 5, 6, 2, 3]

↑i

stack (index:height)(stack)

1:1

best(vars)

Step 1/41 pops bar 0 (height 2): width 1 (no shorter bar left of it), area 2. Push 1.

Approach 2

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

class Solution {
    public int largestRectangleArea(int[] h) {
        Deque<Integer> stack = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i <= h.length; i++) {
            int cur = (i == h.length) ? 0 : h[i];             // sentinel flushes the stack
            while (!stack.isEmpty() && cur < h[stack.peek()]) {
                int height = h[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                best = Math.max(best, height * (i - left - 1));
            }
            stack.push(i);
        }
        return best;
    }
}

Verdict: Each bar is pushed and popped once.

Before you submit

Edge cases and common mistakes

Test these inputs

Increasing heights (all resolved by the sentinel)
All equal heights
Zeros

Mistakes people make

Forgetting the final flush, missing rectangles that reach the end.
Using the popped index as the left boundary instead of the new top.

Interview

Follow-up questions

How does this solve Maximal Rectangle in a binary matrix?

Command Palette