Largest Rectangle in Histogram
Hard · Monotonic Stack · Array · Stack · Monotonic Stack
Problem
You are given heights, a histogram of bars that stand side by side: bar i is 1 wide and heights[i] tall.
Return the area of the largest rectangle that fits entirely inside the histogram. The rectangle covers a contiguous run of bars, sits on the baseline, and can be no taller than the shortest bar in its run.
Examples
Input: heights = [2,1,5,6,2,3] Output: 10
The bars of height 5 and 6 together hold a rectangle 5 tall and 2 wide.
Input: heights = [2,4] Output: 4
The 4 alone gives 4; both bars together give only 2 × 2 = 4 as well.
Constraints
- 1 <= len(heights) <= 10^5
- 0 <= heights[i] <= 10^4
Approaches
- Brute force: every run of bars — time O(n²), space O(1)
Follow-up
Can you reuse this to find the largest rectangle made only of 1s in a binary matrix (LeetCode 85)? Treat each row as the base of a histogram.
Related problems
Start free on Cariara · Coding problems · System design studio
