Stage 4: Advanced Techniques·Monotonic Stack & Deque

Hard#8410 min readMonotonic StackArraysLeetCode

Largest Rectangle in Histogram

Monotonic stack with sentinels

THE canonical mono stack problem. Must solve in under 15 minutes.

Published Apr 16, 2026

Problem

Given an array heights representing the bar heights of a histogram (each bar has unit width), return the area of the largest rectangle that fits entirely within the histogram.

Input

heights = [2, 1, 5, 6, 2, 3]

Output

Explanation

Bars at indices 2 and 3 (heights 5 and 6) form a 5×2 rectangle.

Input

heights = [2, 4]

Output

Explanation

Either the 4×1 bar or a 2×2 spanning both bars.

Intuition

For every bar h[i], the tallest rectangle that uses h[i] as its full height is determined by how far left and right you can extend while staying at least as tall as h[i].

If we knew, for each bar, L[i] = index of the first strictly smaller bar on the left (or -1) and R[i] = index of the first strictly smaller bar on the right (or n), the answer is max_i h[i] * (R[i] - L[i] - 1).

Finding L and R is exactly the "nearest smaller on each side" pattern — one pass each with a monotonic stack. We can also fold both passes into a single pass with a sentinel at the end.

Approach

Brute Expand

TimeO(n²)

SpaceO(1)

For each bar i, scan outward in both directions while every bar is at least h[i]. Track the widest stretch and compute h[i] * width.

Simple to write, good for a baseline, blows up at n = 10^5.

impl Solution {
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let n = heights.len();
        let mut best = 0;

        for i in 0..n {
            let h = heights[i];
            let mut l = i;
            while l > 0 && heights[l - 1] >= h {
                l -= 1;
            }
            let mut r = i;
            while r + 1 < n && heights[r + 1] >= h {
                r += 1;
            }
            let area = h * ((r - l + 1) as i32);
            if area > best {
                best = area;
            }
        }

        best
    }
}

Rust · runnable

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  let best = 0;

  for (let i = 0; i < n; i++) {
    const h = heights[i];
    let l = i;
    while (l > 0 && heights[l - 1] >= h) l--;
    let r = i;
    while (r + 1 < n && heights[r + 1] >= h) r++;
    const area = h * (r - l + 1);
    if (area > best) best = area;
  }

  return best;
}

TypeScript · runnable

Divide and Conquer

TimeO(n log n) avg, O(n²) worst

SpaceO(n)

The tallest rectangle in any range either:

uses the minimum bar of that range at full width (height = min, width = range length), or
lives entirely to the left of the minimum, or entirely to the right.

Recursively solve left and right, return the max of the three candidates. Each call does O(range) work to find the min — giving O(n log n) on balanced splits and O(n²) when the input is sorted.

impl Solution {
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        fn solve(h: &[i32], lo: usize, hi: usize) -> i32 {
            if lo > hi {
                return 0;
            }
            let mut min_idx = lo;
            for i in (lo + 1)..=hi {
                if h[i] < h[min_idx] {
                    min_idx= i;
                }
            }
            let span= h[min_idx] * ((hi - lo + 1) as i32);
            let left= if min_idx > lo { solve(h, lo, min_idx - 1) } else { 0 };
            let right = if min_idx < hi { solve(h, min_idx + 1, hi) } else { 0 };
            span.max(left).max(right)
        }

        if heights.is_empty() {
            return 0;
        }
        solve(&heights, 0, heights.len() - 1)
    }
}

Rust · runnable

function largestRectangleArea(heights: number[]): number {
  function solve(lo: number, hi: number): number {
    if (lo > hi) return 0;
    let minIdx = lo;
    for (let i = lo + 1; i <= hi; i++) {
      if (heights[i] < heights[minIdx]) minIdx = i;
    }
    const span = heights[minIdx] * (hi - lo + 1);
    const left = minIdx > lo ? solve(lo, minIdx - 1) : 0;
    const right = minIdx < hi ? solve(minIdx + 1, hi) : 0;
    return Math.max(span, left, right);
  }

  if (heights.length === 0) return 0;
  return solve(0, heights.length - 1);
}

TypeScript · runnable

Monotonic Stack with Sentinel

TimeO(n)

SpaceO(n)

Recommended

Walk i from 0 to n, treating position n as a virtual bar of height 0 that forces everything left on the stack to flush.

The stack stores indices of increasing heights. When the current bar is strictly shorter than the bar at the top of the stack:

Pop index j — its rectangle uses heights[j] as its height.
Width equals i - stack.top() - 1 if the stack isn't empty after popping (bars between the new top and i are all >= heights[j]). If the stack is now empty, width is i — heights[j] extends all the way to the left edge.

Each index is pushed once and popped once, so the whole thing runs in O(n) — including the sentinel pop at the end.

impl Solution {
    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        let n = heights.len();
        let mut stack: Vec<usize> = Vec::with_capacity(n + 1);
        let mut best: i32 = 0;

        for i in 0..=n {
            let cur = if i == n { 0 } else { heights[i] };

            while let Some(&top) = stack.last() {
                if heights[top] > cur {
                    stack.pop();
                    let h = heights[top];
                    let width = match stack.last() {
                        Some(&left) => (i - left - 1) as i32,
                        None => i as i32,
                    };
                    let area = h * width;
                    if area > best {
                        best = area;
                    }
                } else {
                    break;
                }
            }

            stack.push(i);
        }

        best
    }
}

Rust · runnable

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const stack: number[] = [];
  let best = 0;

  for (let i = 0; i <= n; i++) {
    const cur = i === n ? 0 : heights[i];

    while (stack.length > 0 && heights[stack[stack.length - 1]] > cur) {
      const top = stack.pop()!;
      const h = heights[top];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      const area = h * width;
      if (area > best) best = area;
    }

    stack.push(i);
  }

  return best;
}

TypeScript · runnable

Language notes:

Sentinel at i = n — treating index n as a 0-height bar forces every remaining stack entry to pop, so we don't need a separate "drain the stack" loop.
Width formula — once we pop top, the new stack top is the first strictly smaller bar on the left. Everything between it and i is at least heights[top]. The -1 excludes that smaller-left-boundary itself.
Strict > on pop — using >= would still produce the correct max because equal-height bars produce the same or a wider rectangle at the next pop; the strict version is marginally fewer writes.

Trace

Monotonic stack walking heights = [2, 1, 5, 6, 2, 3] (+ sentinel at i = 6):

i	cur	pops (h, width, area)	stack after
0	2	—	[0]
1	1	pop 0 → (2, 1, 2)	[1]
2	5	—	[1, 2]
3	6	—	[1, 2, 3]
4	2	pop 3 → (6, 1, 6), pop 2 → (5, 2, 10)	[1, 4]
5	3	—	[1, 4, 5]
6	0	pop 5 → (3, 1, 3), pop 4 → (2, 4, 8), pop 1 → (1, 6, 6)	[6]

Best area = max(2, 6, 10, 3, 8, 6) = 10.

Edge cases

All equal heights [3, 3, 3, 3] — nothing pops until the sentinel; then the last pop computes 3 × 4 = 12.
Strictly decreasing [5, 4, 3, 2, 1] — every new bar pops the previous; best rectangle is 3 × 3 = 9 (indices 2..4).
Strictly increasing — stack keeps growing; sentinel flushes everything at the end.
Single bar — area equals the bar's height.
Zero-height bar — immediately flushes the stack as if we'd hit the sentinel.

💡

Tip

The width formula i - stack.top() - 1 after the pop is where most incorrect solutions break. Trace it once with pen and paper — the two neighbors that bound the popped bar on the left and right are the previous stack element and the current i, exclusive.

Takeaway

This is the canonical monotonic stack problem. Every "largest rectangle / widest span / maximum area" question with a 1D profile reduces to finding the nearest smaller element on each side.

The technique extends directly to 2D in #85 (Maximal Rectangle) by reducing each row of a binary grid to a histogram problem, and it's the core of several order-book depth-analysis queries in trading systems.

Hard#85

Maximal Rectangle

Row-by-row histogram heights, then apply #84 per row.

Hard#239

Sliding Window Maximum

Monotonic deque. Maintain decreasing order; front is always the max.

Easy#496

Next Greater Element I

The basic pattern. Process right to left, stack holds candidates.