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, Python, C++ and JavaScript, 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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(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.

  1. For each i, move l left and r right while heights >= heights[i].
  2. area = heights[i] * (r - l - 1).
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.

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