Largest Rectangle in Histogram

Problem

Given bar heights (unit width), return the area of the largest rectangle that fits under the histogram.

Constraints

• 1 ≤ n ≤ 10⁵

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def largestRectangleArea(self, heights):
        st = []
        best = 0
        for i, h in enumerate(heights + [0]):
            while st and heights[st[-1]] >= h:
                height = heights[st.pop()]
                width = i if not st else i - st[-1] - 1
                best = max(best, height * width)
            st.append(i)
        return best

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.