Largest Rectangle in Histogram

HardMonotonic Stack/QueueNeetCode 150SeniorOpen on LeetCodeUpdated Nov 11, 2026

You're given an array heights where heights[i] is the height of a bar of width 1 in a histogram, with the bars standing side by side. Return the area of the largest rectangle that fits entirely inside the histogram. The rectangle must cover a contiguous run of bars, and it can be no taller than the shortest bar in that run.

Examples

heights = [2,1,5,6,2,3] returns 10

Height 5 across bars 2 and 3: area 5 x 2 = 10.

The bars at indices 2 and 3 (heights 5 and 6) are both at least 5 tall, so a rectangle of height 5 and width 2 fits, for area 10. Going wider costs height: height 2 across indices 2 to 5 gives only 8, and height 1 across all six bars gives 6.

heights = [2,4] returns 4

The tall bar alone gives 4 x 1 = 4, and both bars together at height 2 give 2 x 2 = 4. Either way the best area is 4.

heights = [2,1,2] returns 3

Height 1 across all three bars: area 3.

Each bar of height 2 on its own gives only 2. Here the shortest bar wins: height 1 stretched across all three bars gives 3.

Constraints

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

Hints

Hint 1

For each bar, you want the widest stretch in which it is the smallest, could a stack remember pending bars cheaply?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

The best rectangle uses some bar's full height and stretches left and right until it hits a shorter bar. Keep a stack of indices whose heights increase. When bar i is shorter than the top, pop it: its rectangle ends at i - 1 and starts just after the new top (or at 0 if the stack is empty), so its width is i - top - 1 or i. A sentinel height of 0 at i = n pops every bar left over. Each index is pushed and popped once.

Time

O(n)

Space

O(n)

Pitfall

Skipping the final height-0 pass leaves bars on the stack unmeasured: for [1,2,3] you'd return 0 instead of 4. And when the stack empties after a pop, the width is i (the rectangle reaches index 0), not i - 1.

Solutions

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

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