Stack crash course ↗ · 22

84. Largest Rectangle in Histogram

Find the largest axis-aligned rectangle that fits inside a histogram of bars with given heights. A monotonic increasing stack lets you compute, in a single pass, the farthest each bar can extend to the left — turning an O(n²) brute force into O(n).

● HardMonotonic StackArrayTypeScript

PROBLEM What we're solving

Given an array heights where heights[i] is the height of the i-th bar (width 1), return the area of the largest rectangle that fits entirely within the histogram.

Example: heights = [2,1,5,6,2,3]. The largest rectangle uses bars at indices 2 and 3 (heights 5 and 6), both limited to height 5, giving area 5 × 2 = 10. Answer: 10.

The tricky part: a rectangle can span multiple bars but is limited to the shortest bar in that span. You need to try all possible heights efficiently.

KEY IDEA Each bar is the bottleneck for exactly one maximal rectangle

Insight → For every bar, consider it as the height-limiting bar of some rectangle. That rectangle extends left as far as bars remain taller, and right as far as bars remain taller. A monotonic increasing stacktells you exactly when a bar's "right boundary" is reached: the moment a shorter bar arrives, every taller bar in the stack has found its right wall. Pop each one and compute its area in O(1). Every bar is pushed once and popped once → O(n) total.

RECIPE Monotonic stack: push, pop-and-compute, sentinel flush

0 · Stack shape. Maintain a stack of [startIndex, height] pairs in strictly increasing order of height. The start index records how far left this bar can still extend (it may be farther than its actual column).
1 · Scan with a sentinel. Iterate i from 0 to n inclusive. At i = n use a synthetic height of 0 so every remaining stack entry gets flushed without special-casing.
2 · Pop loop. While the stack top has height >= curH, pop it. The popped bar spans from its recorded startIndex to i - 1, giving width = i - startIndex. Update maxArea if h × width is larger. Also set start = startIndex — the current bar inherits this left boundary because it was unblocked all along.
3 · Push. Push [start, curH] onto the stack. The start may be to the left of i if we popped any taller bars.
4 · Return. After the sentinel flush, return maxArea.

Classic confusion → People track only the bar's own index, not its effective left boundary. When bar i pops bars to its left, bar i's own rectangle can extend all the way back — you must inherit the start index of the last popped bar. Forgetting this gives a wrong (too small) area for bars that "absorb" prior taller ones.

COST Complexity & alternatives

Brute force (all pairs)

O(n²)

For each left boundary, scan right tracking the running min height.

Monotonic stack

O(n)

Each bar pushed once and popped once. O(n) auxiliary space.

Space note

The stack holds at most n entries (one per bar) so space is O(n). There is no O(1)-space solution known for the general case — the stack is essential. The sentinel trick (appending a virtual height-0 bar) cleanly avoids a post-loop flush and is idiomatic.

Pattern transfer → The same monotonic-stack skeleton powers Trapping Rain Water (LC 42 — find the water above each bar), Daily Temperatures (LC 739 — next greater element), Maximal Rectangle (LC 85 — reduce each row to a histogram then apply LC 84), and Sum of Subarray Minimums (LC 907).

RUN IT Monotonic stack: push and pop to find the largest rectangle

heights =

step 0 / 20

STARTHeights: 2, 1, 5, 6, 2, 3. We scan left to right, maintaining a monotonic increasing stack of (index, height) pairs.

1function largestRectangleArea(heights: number[]): number {
2  // Stack stores [startIndex, height] pairs.
3  // Invariant: heights in the stack are always strictly increasing.
4▶  const stack: [number, number][] = [];
5▶  let maxArea = 0;
6 
7  for (let i = 0; i <= heights.length; i++) {
8    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
9    let start = i;
10 
11    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
12      const [idx, h] = stack.pop()!;
13      const width = i - idx;
14      maxArea = Math.max(maxArea, h * width);
15      start = idx; // this bar's left boundary extends back to here
16    }
17 
18    stack.push([start, curH]);
19  }
20 
21  return maxArea;
22}

Stack (idx:h):

empty

Max area:

—

curH:

—

start:

—

current barin stackbeing poppedbest rectangle

slowfast

TYPESCRIPT The solution, annotated

largestRectangleArea.ts
function largestRectangleArea(heights: number[]): number {
  // Stack stores [startIndex, height] pairs.
  // Invariant: heights in the stack are always strictly increasing.
  const stack: [number, number][] = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
    let start = i;

    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
      const [idx, h] = stack.pop()!;
      const width = i - idx;
      maxArea = Math.max(maxArea, h * width);
      start = idx; // this bar's left boundary extends back to here
    }

    stack.push([start, curH]);
  }

  return maxArea;
}

Reading it block by block

Lines 3–4 — setup. The stack holds [startIndex, height]pairs. The start index is the leftmost column this bar's height can still cover. maxArea accumulates the running best.

Line 7 — loop with sentinel. Iterating to heights.length inclusive lets us treat index n as a virtual bar of height 0. This forces every remaining stack entry to pop and get measured without needing a separate post-loop pass.

Lines 9–14 — pop loop. As long as the top of the stack is at least as tall as the current bar, it has found its right boundary. Pop it, compute width = i - idx(the popped bar's left boundary), and update the max. Record start = idx so the current bar inherits the left boundary of the last popped entry — the rectangle of the current bar extends that far back too.

Line 16 — push. Push [start, curH]. If we popped any bars, start is to the left of i, encoding that this bar's potential rectangle begins there.

Line 19 — return. After the sentinel flushes the stack, maxAreaholds the answer. Every possible "limiting height" bar has been considered exactly once.

Complexity → O(n) time — the inner while loop looks O(k) per iteration, but each bar is pushed exactly once and popped at most once, so the total work across all iterations is O(n). O(n) space for the stack.

INTERVIEWFollow-ups they'll ask

"What if all heights are equal?" The entire array pops at the sentinel — one rectangle of area h × n. The algorithm handles it correctly; just verify with [3,3,3] → 9.
"How does Maximal Rectangle (LC 85) reduce to this?" Build a running histogram row by row: dp[j] = number of consecutive filled cells ending at the current row in column j. Call largestRectangleArea(dp) for each row.
"Can you do it without the sentinel?" Yes — after the main loop, flush the stack manually with the same pop-and-compute logic. The sentinel is cleaner but not strictly necessary.
"Return the actual rectangle coordinates, not just the area?" Track bestL, bestR, and bestH whenever you update maxArea.
"What is the brute-force, and why is this better?" Fix every left boundary, scan right tracking minH, compute area — O(n²). The stack removes the need to rescan by recording each bar's left boundary at push time.

OPTIMAL Monotonic Stack

largestRectangleArea.ts
function largestRectangleArea(heights: number[]): number {
  // Stack stores [startIndex, height] pairs.
  // Invariant: heights in the stack are always strictly increasing.
  const stack: [number, number][] = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
    let start = i;

    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
      const [idx, h] = stack.pop()!;
      const width = i - idx;
      maxArea = Math.max(maxArea, h * width);
      start = idx; // this bar's left boundary extends back to here
    }

    stack.push([start, curH]);
  }

  return maxArea;
}

ALT 1 Nearest-smaller boundaries (two passes)

O(n) time · O(n) space

Precompute, for each bar, the index of the nearest strictly-shorter bar to its left and to its right, then every bar's maximal width is just the gap between those two walls.

approach-2.ts
function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  if (n === 0) return 0;

  // left[i] = index of nearest bar to the LEFT that is strictly shorter than heights[i];
  //           -1 if no such bar exists.
  const left: number[] = new Array<number>(n);
  // right[i] = index of nearest bar to the RIGHT that is strictly shorter; n if none.
  const right: number[] = new Array<number>(n);

  // Left pass: a monotonic stack of indices with strictly increasing heights.
  const leftStack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (leftStack.length > 0 && heights[leftStack[leftStack.length - 1]] >= heights[i]) {
      leftStack.pop();
    }
    left[i] = leftStack.length === 0 ? -1 : leftStack[leftStack.length - 1];
    leftStack.push(i);
  }

  // Right pass: same idea, scanning from the right.
  const rightStack: number[] = [];
  for (let i = n - 1; i >= 0; i--) {
    while (rightStack.length > 0 && heights[rightStack[rightStack.length - 1]] >= heights[i]) {
      rightStack.pop();
    }
    right[i] = rightStack.length === 0 ? n : rightStack[rightStack.length - 1];
    rightStack.push(i);
  }

  // Each bar limits a rectangle spanning (left[i], right[i]) exclusive on both ends.
  let maxArea = 0;
  for (let i = 0; i < n; i++) {
    const width = right[i] - left[i] - 1;
    maxArea = Math.max(maxArea, heights[i] * width);
  }
  return maxArea;
}

Note → Functionally equivalent to the one-pass stack but often easier to reason about: the boundary arrays make the "how far can this bar extend" question explicit. The strict-inequality choice (>= when popping) avoids double-counting equal-height plateaus.

ALT 2 Brute force (expand each bar)

O(n²) time · O(1) space

Treat every bar as the limiting height and physically walk outward in both directions while the neighbouring bars are at least as tall.

approach-3.ts
function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  let maxArea = 0;

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

    // Expand left while bars stay at least as tall as h.
    let lo = i;
    while (lo - 1 >= 0 && heights[lo - 1] >= h) {
      lo--;
    }

    // Expand right while bars stay at least as tall as h.
    let hi = i;
    while (hi + 1 < n && heights[hi + 1] >= h) {
      hi++;
    }

    const width = hi - lo + 1;
    maxArea = Math.max(maxArea, h * width);
  }

  return maxArea;
}

Note → The simplest correct approach and a good sanity check: for each bar it finds the widest run of bars no shorter than itself. Worst case (a sorted or all-equal histogram) every expansion sweeps most of the array, giving O(n²) — fine for small inputs, too slow at scale.

MNEMONIC The one-liner

"When a shorter bar arrives, every taller bar behind it has found its right wall — pop, measure, inherit the boundary."

TRIGGERS When you see _ → reach for _

"largest / maximum rectangle in histogram"	monotonic increasing stack
each element is the bottleneck height for some subarray	pop when shorter arrives, compute width
"maximal rectangle in binary matrix"	histogram row-by-row + LC 84
next smaller element with area calculation	stack stores [startIdx, height]

SKELETON The reusable shape

skeleton.ts
const stack: [number, number][] = []; // [startIndex, height]
let maxArea = 0;

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

FLASHCARDS Tap to flip

What does each stack entry store, and why the start index?

[startIndex, height]. The start index is the leftmost column this bar's height can still cover — it may be to the left of the bar's actual column because taller bars were popped out of the way.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For heights = [2,1,5,6,2,3], what is the largest rectangle area?

QUESTION 02

What invariant does the monotonic stack maintain?

QUESTION 03

Why is a sentinel value of 0 appended at index n?

QUESTION 04

What is the time complexity of the monotonic-stack solution?

QUESTION 05

When we pop a bar with recorded startIndex = 2 at current index i = 5 and height h = 4, what area do we compute?

QUESTION 06

Why must the current bar inherit the start index of the last popped bar?

QUESTION 07

Which problem directly reduces to running largestRectangleArea once per row?

QUESTION 08

#84 · Largest Rectangle in HistogramA monotonic increasing stack of (startIndex, height) pairs computes the maximum rectangle in O(n): when a shorter bar is encountered, pop and extend each taller bar's width back to the popped position.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Each bar is the bottleneck for exactly one maximal rectangle

RECIPE Monotonic stack: push, pop-and-compute, sentinel flush

COST Complexity & alternatives

Space note

RUN IT Monotonic stack: push and pop to find the largest rectangle

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Monotonic Stack

ALT 1 Nearest-smaller boundaries (two passes)

ALT 2 Brute force (expand each bar)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _