02. Largest Rectangle in Histogram

Difficulty:HardPattern:Monotonic StackTime:O(n)Space:O(n)

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.

How It Works & Algorithmic Design

Solves using Monotonic Increasing Stack:

Sentinel Padding: Append height 0 at end of array to flush stack elements at conclusion.
Stack Stores Indices: Maintain stack keeping corresponding heights in increasing order.
Loop Bar Heights $i$:
- While stack.top height is greater than heights[i]:
  - Pop height h = heights[stack.pop()].
  - Width = stack.isEmpty ? i : i - stack.top - 1.
  - maxArea = Math.max(maxArea, h * width).
- Push current index $i$.

Why This Approach Works Best

Monotonic stack processes every bar height boundary in single-pass linear $O(n)$ time and $O(n)$ space.

Example Walkthrough

Input Heights: [2, 1, 5, 6, 2, 3]

Histogram bar heights.

Max Area Rectangle: Bars at idx 2 and 3 (heights 5, 6) form 5 * 2 = 10 area.

Largest rectangle bounded by height 5.

Output: 10

Max rectangular area.

Answer: Largest Rectangle in Histogram implementation

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

💡 Use a monotonic increasing stack to calculate max rectangular area bounded by bar heights.

Key Takeaways

Stack elements are strictly increasing in height.
Trailing zero height flushes remaining stack elements.
Single pass linear $O(n)$ time and $O(n)$ space.