Largest Rectangle in Histogram

HardMonotonic Stack🧩 Monotonic Stack LeetCode #84 ↗Updated Oct 30, 2026

Problem

A histogram is given as heights, where every bar has width 1 and bars stand side by side. Find the area of the largest axis-aligned rectangle that fits completely inside the histogram.

Input[2,1,5,6,2,3]Output10

Input[2,4]Output4

1 ≤ n ≤ 10⁵ · 0 ≤ heights[i] ≤ 10⁴

Try it yourself

Java

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

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The best rectangle is limited by its shortest bar. So for every bar, stretch it left and right until the first strictly shorter bar on each side: area = h[i] × (right - left - 1). A monotonic stack finds both walls.

PatternMonotonic Stack

Instinct Each element needs its nearest bigger or smaller neighbour (next warmer day, span, widest bar) - keep a sorted stack of waiting indices.

Memory hack Tall people block the view - a newcomer kicks out everyone shorter waiting behind, and each kicked-out person just found their answer.

Open the Monotonic Stack guide →

Approaches

Brute ForceAll Ranges with Running Minimum

Time O(n²)Space O(1)

Fix a left edge i and extend the right edge j one bar at a time, tracking the minimum height of [i..j]. The rectangle over that range has area min × (j - i + 1).

Java

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

Simple, but ~5·10⁹ steps at n = 10⁵ — TLE.

BetterNearest Smaller on Each Side (Two Passes)

Time O(n)Space O(n)

Compute left[i] / right[i] = index of the nearest strictly shorter bar on each side, using a stack in a left-to-right and a right-to-left pass. Bar i then spans right[i] - left[i] - 1.

Java

public int largestRectangleArea(int[] heights) {
    int n = heights.length, maxArea = 0;
    int[] left = new int[n], right = new int[n];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && heights[st.peek()] >= heights[i]) st.pop();
        left[i] = st.isEmpty() ? -1 : st.peek();
        st.push(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && heights[st.peek()] >= heights[i]) st.pop();
        right[i] = st.isEmpty() ? n : st.peek();
        st.push(i);
    }
    for (int i = 0; i < n; i++) {
        maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
    }
    return maxArea;
}

Linear and easy to reason about, but three passes and two extra arrays.

OptimalOne-Pass Increasing Stack + Sentinel

Time O(n)Space O(n)

Keep indices with increasing heights. When bar i is not taller than the top, the top has found its right wall (i); its left wall is the element below it. Pop, score, repeat. A height-0 sentinel at i = n flushes the stack.

Java

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

Dry run[2,1,5,6,2,3]

i currents on stack changed

i=0
2
i s
1

5

6

2

3

push 0
i=1
2

1
i s
5

6

2

3

pop 2: 2×1=2
i=3
2

1
s
5
s
6
i s
2

3

push 5, 6
i=4
2

1
s
5

6

2
i s
3

6×1=6, 5×2=10
i=5
2

1
s
5

6

2
s
3
i s
push 3
i=6
2

1

5

6

2

3

flush: 3, 8, 6 → 10 ✔

Single pass; each index pushed and popped once — the classic answer.

Pro tip

Same trick solves Maximal Rectangle (85): build a histogram per matrix row and run this function on it.

At a glance

Level	Approach	Time	Space
Brute Force	All Ranges with Running Minimum	`O(n²)`	`O(1)`
Better	Nearest Smaller on Each Side (Two Passes)	`O(n)`	`O(n)`
Optimal	One-Pass Increasing Stack + Sentinel	`O(n)`	`O(n)`

Common pitfalls

Forgetting to process bars left on the stack at the end — the sentinel handles it.
Width off-by-one: it is i - left - 1, with left = -1 on an empty stack.
Measuring width from the popped index instead of the new stack top.

Interview tips

Reframe first: “each bar as the shortest one — how far can it extend?”
Present the two-pass version, then fuse it into one pass with the sentinel.
Walk through [2,1,5,6,2,3]; it exercises every branch.

Pattern

Monotonic increasing stack → span/area problems bounded by the nearest smaller element on both sides.

My notes saved in this browser