Largest Rectangle in Histogram [Hard] — Monotonic Stack

Problem Statement

Given an array of heights representing a histogram, find the area of the largest rectangle that can be formed.

Input: [2,1,5,6,2,3] → Output: 10

Intuition

Monotonic increasing stack of indices. When a bar shorter than the top is found, pop and compute: width = i - stack.top() - 1 (or i if stack empty), area = height[popped] × width.

Solutions

C++

int largestRectangleArea(vector<int>& heights) {
    stack<int> stk;
    heights.push_back(0); // sentinel
    int maxArea=0;
    for (int i=0;i<heights.size();i++) {
        while (!stk.empty()&&heights[i]<heights[stk.top()]) {
            int h=heights[stk.top()]; stk.pop();
            int w=stk.empty()?i:i-stk.top()-1;
            maxArea=max(maxArea,h*w);
        }
        stk.push(i);
    }
    return maxArea;
}

Java

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

JavaScript

var largestRectangleArea = function(heights) {
    heights.push(0);
    const stk=[], n=heights.length;
    let maxArea=0;
    for (let i=0;i<n;i++) {
        while (stk.length&&heights[i]<heights[stk.at(-1)]) {
            const h=heights[stk.pop()];
            const w=stk.length?i-stk.at(-1)-1:i;
            maxArea=Math.max(maxArea,h*w);
        }
        stk.push(i);
    }
    return maxArea;
};

Python

def largestRectangleArea(heights: list[int]) -> int:
    heights.append(0)  # sentinel
    stack = []
    max_area = 0
    for i, h in enumerate(heights):
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # restore
    return max_area

Complexity

Time: O(n) — each bar pushed and popped once
Space: O(n)