Largest Rectangle in Histogram

Share

Given heights array representing histogram bars, find area of largest rectangle.

Example 1
Input: heights=[2,1,5,6,2,3] → Output: 10
Example 2
Input: heights=[2,4] → Output: 4

Solution Approach

Monotonic stack: maintain increasing stack. When height decreases, calculate area with popped bar as smallest.

  • Use stack (storing indices)
  • For each bar: while stack top height > current, pop
  • Width = current_index - stack_top_index - 1
  • Area = popped_height * width; track max
  • Process remaining stack after loop
Java
public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int max = 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 width = stack.isEmpty() ? i : i - stack.peek() - 1;
            max = Math.max(max, height * width);
        }
        stack.push(i);
    }
    return max;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)