Largest Rectangle Histogram | Monotonic Stack | Stack

Overview

Largest rectangle in histogram: given an array of bar heights, find the maximum area of a rectangle that fits under the histogram (contiguous bars, rectangle height = minimum bar in the range). For each bar at index i with height h, the largest rectangle with h as the minimum spans from the previous smaller index (or -1) to the next smaller index (or n). Width = (nextSmaller - prevSmaller - 1); area = h * width. Use monotonic stacks to get previous/next smaller for each index in O(n).

When to Use

Largest rectangle under histogram — classic; one or two stacks.
Maximal rectangle in a 0-1 matrix — treat each row as a histogram (heights of 1s from bottom); run this algorithm per row.
Largest rectangle with a given constraint — same "previous/next smaller" idea.

How It Works

Next smaller: scan left to right; increasing stack (by height); when you pop, current i is next smaller for popped index.
Previous smaller: scan right to left, or scan left to right and when popping, the new top is previous smaller for the popped index (with care for boundaries).
Single-stack trick: process indices 0..n (use h=0 at index n to force all pops). When you pop idx, the left boundary of the rectangle with height heights[idx] is (stack[top] + 1) and right boundary is (i - 1); width = (i - 1) - (stack[top] + 1) + 1 = i - stack[top] - 1. If stack empty after pop, left boundary is 0.

Example 1: Single Stack (One Pass)

When we pop an index, we know its "next smaller" is the current i. The "previous smaller" is the index now on top of the stack (or -1 if stack empty). So width = i - stack[top] - 1 (or i if stack empty).

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

Time: O(n). Space: O(n).

Example 2: Two Pass (Prev and Next Smaller Arrays)

First pass: compute nextSmaller[i] (first j > i with heights[j] < heights[i], else n). Second pass: compute prevSmaller[i] (last j < i with heights[j] < heights[i], else -1). Then for each i: width = nextSmaller[i] - prevSmaller[i] - 1; area = heights[i] * width.

function largestRectangleAreaTwoPass(heights: number[]): number {
  const n = heights.length;
  const nextSmaller = new Array(n).fill(n);
  const prevSmaller = new Array(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      nextSmaller[stack.pop()!] = i;
    }
    if (stack.length > 0) prevSmaller[i] = stack[stack.length - 1];
    stack.push(i);
  }
  let maxArea = 0;
  for (let i = 0; i < n; i++) {
    const w = nextSmaller[i] - prevSmaller[i] - 1;
    maxArea = Math.max(maxArea, heights[i] * w);
  }
  return maxArea;
}

Example 3: Step-by-Step Trace

heights = [2,1,5,6,2,3]. i=0: push 0. i=1: h=1 < 2, pop 0, width=1, area=2; push 1. i=2,3: push 2,3. i=4: h=2 < 6, pop 3, width=1, area=6; h=2 < 5, pop 2, width=4-1-1=2, area=10; push 4. i=5: push 5. i=6 (sentinel h=0): pop 5, width=6-4-1=1, area=3; pop 4, width=6-1-1=4, area=8; pop 1, width=6, area=6. Max area = 10.

Example 4: Edge Cases

Empty array: return 0.
Single bar [h]: width=1, area=h.
Strictly increasing: each bar’s next smaller is n, prev smaller is i-1; width = n - (i-1) - 1 = n - i; e.g. [1,2,3] gives areas 3,4,3; max 4.
Strictly decreasing: sentinel at n forces all pops; each rectangle extends left to 0 or to previous smaller.

Example 5: Return the Bounds of the Max Rectangle

Instead of just the area, return (left, right, height). Track the idx and width when you update maxArea; height = heights[idx], left = idx - width + 1 (or stack[top]+1 when stack non-empty), right = i - 1 (or i - 1 when popping). Adjust for the sentinel pass so right = i - 1.

Summary

Largest rectangle: for each bar, extend left to previous smaller and right to next smaller; area = height * width. Single stack with sentinel h=0 at n, or two-pass prev/next smaller. See Monotonic Stack, Next Greater Element.

Largest Rectangle in Histogram