Largest Rectangle in Histogram

Difficulty: Hard

Problem

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. The rectangle must be formed by contiguous bars.

Example

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle has area = 10 and is formed by bars at indices 2 and 3 (heights 5 and 6), spanning width 2: min(5,6) × 2 = 5 × 2 = 10.

Brute-force approach

For each bar, expand left and right to find how far the rectangle of that bar's height can extend. Calculate area and track the maximum.

Steps

  1. For each bar i:
  2. Expand left while bars have height ≥ heights[i]
  3. Expand right while bars have height ≥ heights[i]
  4. area = heights[i] × (right - left + 1)
  5. maxArea = max(maxArea, area)

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • For each bar, expanding left and right is O(n) in the worst case
  • Total: O(n²) — too slow for large inputs
  • Redundant: neighboring bars re-check overlapping ranges

Optimal approach

Key insight: A bar's rectangle ends when a shorter bar appears to its right. The stack tracks bars that haven't found their right boundary yet.

Use a monotonic increasing stack of indices. When a shorter bar is encountered, pop taller bars and calculate their areas using the current index as the right boundary.

Steps

  1. Initialize empty stack and maxArea = 0
  2. For each index i (including a virtual index n with height 0):
  3. While stack not empty AND current height < height at stack top:
  4. Pop the top index, get its height h
  5. Width = i - stack.top - 1 (or i if stack empty)
  6. maxArea = max(maxArea, h × width)
  7. Push i onto stack
  8. Return maxArea

Time complexity: O(n) · Space complexity: O(n)