Largest Rectangle in Histogram

Hard Problem 39 of 151 Java and Python

Problem

Given an array heights of bar heights in a histogram where every bar is 1 unit wide, return the area of the largest rectangle that fits inside the histogram.

Example 1

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

Example 2

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

Constraints

1 ≤ heights.length ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Explanation

The best rectangle has the height of some bar i, and stretches left and right until it meets a shorter bar. So for each bar you need the nearest shorter bar on each side.

An increasing stack finds both at once: when bar i is shorter than the top, the top cannot extend further right. Its left limit is the bar below it on the stack. Pop it and compute its rectangle.

Approach 1 · Naive

Every start, track the minimum

Time O(n²)
Space O(1)

For each start i, extend to the right while tracking the lowest bar; the rectangle is min × width.

For each i, set low = heights[i].
For j ≥ i, update low = min(low, heights[j]) and the best with low × (j - i + 1).

Java

class Solution {
    public int largestRectangleArea(int[] heights) {
        int best = 0;
        for (int i = 0; i < heights.length; i++) {
            int low = heights[i];
            for (int j = i; j < heights.length; j++) {
                low = Math.min(low, heights[j]);
                best = Math.max(best, low * (j - i + 1));
            }
        }
        return best;
    }
}

Python

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        best = 0
        for i in range(len(heights)):
            low = heights[i]
            for j in range(i, len(heights)):
                low = min(low, heights[j])
                best = max(best, low * (j - i + 1))
        return best

Approach 2 · Optimal

Increasing monotonic stack

Time O(n)
Space O(n)

Keep indices of bars in increasing height. When a shorter bar arrives, pop taller bars and compute each one's rectangle: it spans from just after the new stack top to just before the current index.

Loop i from 0 to n, treating heights[n] as 0 so every bar gets popped at the end.
While the stack is not empty and heights[top] >= h: pop top; width = i if the stack is now empty, else i - stack.top - 1; update the best with heights[top] × width.
Push i.

Java

import java.util.*;

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

Python

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

Complexity compared

Approach	Time	Space
Naive Every start, track the minimum	O(n²)	O(1)
Optimal Increasing monotonic stack	O(n)	O(n)

Key takeaways

The sentinel height 0 at the end flushes the stack without extra code.
This is the building block for Maximal Rectangle, which runs it on every row of a binary matrix.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem