Largest Rectangle in Histogram

hardStack63 stepsJava · Python · C++

Find the largest rectangle under a histogram. Keep a stack of bar indices with increasing heights. When a shorter bar arrives, each taller bar popped can extend no further right; its width runs from the new stack top + 1 to the current index − 1.

▶ Watch the animated trace

Traced input: heights = [2, 1, 5, 6, 2, 3] → 10. Original problem: neetcode.io/problems/largest-rectangle-in-histogram

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Each bar is pushed and popped once.

Key idea

For each bar, the best rectangle using its full height stretches until a shorter bar on each side.
An increasing stack gives the left boundary (the element below it) for free.
The bar that pops it is the right boundary.
A sentinel height 0 at the end flushes the stack.

Common mistakes

Computing width as i - popped instead of i - stack.peek() - 1.
Forgetting to flush the stack at the end.
O(n²) expansion from each bar times out.

Solution

Java

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

Python

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

C++

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int best = 0, n = heights.size();
    for (int i = 0; i <= n; i++) {
        int h = i == n ? 0 : heights[i];
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()]; st.pop();
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            best = max(best, height * width);
        }
        st.push(i);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single bar The sentinel pops it with width 1.	`heights = [4]`	`4`
All equal Equal bars stay on the stack; the sentinel pops the first 3 last, and it spans all three bars.	`heights = [3, 3, 3]`	`9`
Increasing 3 × 3 (heights 3, 4, 5).	`heights = [1, 2, 3, 4, 5]`	`9`
Zero height bar The 0 splits the histogram.	`heights = [2, 0, 2]`	`2`