Largest Rectangle in Histogram

Hard Monotonic Stack Monotonic Stack Original on LeetCode

Largest Rectangle in Histogram is a hard monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (increasing monotonic stack), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from brute force up.

Problem

Given bar heights of a histogram where each bar has width 1, return the area of the largest rectangle that fits entirely inside the histogram.

Examples

Example 1

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Why: Bars 5 and 6 give a rectangle of height 5 and width 2.

Example 2

Input: heights = [3, 3, 3]
Output: 9

Constraints

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

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Optimal (increasing monotonic stack)	`O(n)`	`O(n)`

1Brute force

TimeO(n²)

SpaceO(1)

For each bar, expand left and right while neighbours are at least as tall, then compute height × width.

For each i, move l left and r right while heights >= heights[i].
area = heights[i] * (r - l - 1).

Java

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

2Optimal (increasing monotonic stack)

TimeO(n)Each index is pushed and popped once.

SpaceO(n)

Keep indices with increasing heights. When bar i is shorter than the top, the top's rectangle cannot extend right past i. Its left limit is the new top after popping. Pop and compute the area. A sentinel height 0 at the end flushes the stack.

For i in 0..n (use height 0 at i = n):
While the stack is non-empty and heights[top] > h: pop top.
width = stack empty ? i : i - newTop - 1; best = max(best, heights[top] * width).
Push i.

Java

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

Edge cases to test

All bars equal
Strictly increasing bars (the stack empties only at the end)
Zero-height bars

Hints

Hint 1

For each bar, the widest rectangle of exactly its height stretches until a shorter bar on each side.

Hint 2

A bar popped from an increasing stack knows both its left and right limits.

FAQ

What is the best time complexity for Largest Rectangle in Histogram?

Optimal (increasing monotonic stack) runs in O(n) time and O(n) extra space. Each index is pushed and popped once.

Which pattern does Largest Rectangle in Histogram use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Largest Rectangle in Histogram?

Yes. Brute force takes O(n²) time and O(1) space. For each bar, expand left and right while neighbours are at least as tall, then compute height × width.

Which edge cases should I test for Largest Rectangle in Histogram?

All bars equal; Strictly increasing bars (the stack empties only at the end); Zero-height bars.