The Stack Invariant Behind Largest Rectangle in Histogram

Almost every writeup of LeetCode 84 contains this sentence, or something close to it:

The stack holds indices whose heights are strictly increasing from bottom to top.

It is wrong for the code printed underneath it. Run that code on [3, 3, 3, 3] and the stack ends up holding all four indices at once, every one of them the same height. The claim is not a typo either — the rest of the explanation is built on it, and it is the reason people get the equal-bars case wrong when they write the algorithm from memory in an interview.

The algorithm is still correct. The invariant is just one word off, and that word changes what a pop is allowed to conclude. So this post does the thing the claim invites: state the invariant precisely enough that a program can check it, then run the program.

The problem, for reference: heights[i] is the height of the i-th bar, every bar is one unit wide, and you want the area of the largest axis-aligned rectangle that fits inside the histogram. For [2, 1, 5, 6, 2, 3] the answer is 10 — bars 2 and 3 clipped to height 5.

Here is the implementation everything below is measuring.

const largestRectangleArea = (heights) => {
  const stack = [];          // indices; heights at those indices never decrease
  let maxArea = 0;
 
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
 
    while (stack.length > 0 && heights[stack[stack.length - 1]] > h) {
      const height = heights[stack.pop()];
      const left = stack.length > 0 ? stack[stack.length - 1] : -1;
      maxArea = Math.max(maxArea, height * (i - left - 1));
    }
 
    stack.push(i);
  }
 
  return maxArea;
};

The loop runs to heights.length inclusive, and on that last step h is 0. That is the sentinel: a virtual bar of height zero past the right edge, shorter than everything, which flushes whatever is left on the stack. Note that stack.push(i) runs on that step too, so the stack finishes holding the sentinel index, not empty. Most trace tables draw it empty.

The invariant, stated so a program can check it

Three claims, in order of how much work they do:

1. Reading the stack bottom to top, the heights never decrease. Not "strictly increase" — equal neighbours are allowed and common, because the pop test is > and a tie fails it.
2. When index j is popped at step i, every bar strictly between the new stack top and i is at least as tall as heights[j]. So heights[j] * (i - left - 1) is a rectangle that genuinely fits.
3. Therefore no pop ever reports an area larger than the true answer. Some pops report less.

Claim 3 is the one nobody states, and it carries the most weight. The algorithm is safe because it can only under-report, and correct because at least one pop hits the optimum exactly.

The node before push i is where claim 1 is supposed to be true. That is exactly where to assert it.

Checking it 50,000 times

Same loop, with the assertion inserted after the pops and before the push — the only moment when every index on the stack is a real bar. It also counts how often two equal heights sit next to each other on the stack, which is the situation the "strictly increasing" wording says cannot happen.

const assert = (cond, msg) => { if (!cond) throw new Error(msg); };
 
const randomHistogram = (n, maxH) =>
  Array.from({ length: n }, () => Math.floor(Math.random() * maxH));
 
const solveChecked = (heights) => {
  const stack = [];
  let maxArea = 0;
  let ties = 0;
 
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
 
    while (stack.length > 0 && heights[stack[stack.length - 1]] > h) {
      const height = heights[stack.pop()];
      const left = stack.length > 0 ? stack[stack.length - 1] : -1;
      maxArea = Math.max(maxArea, height * (i - left - 1));
    }
 
    for (let k = 1; k < stack.length; k++) {
      assert(
        heights[stack[k]] >= heights[stack[k - 1]],
        `non-decreasing broken at i=${i}: ${JSON.stringify(stack)}`
      );
      if (heights[stack[k]] === heights[stack[k - 1]]) ties++;
    }
 
    stack.push(i);
  }
 
  return { maxArea, ties };
};
 
let tiedStacks = 0;
let checked = 0;
for (let t = 0; t < 50000; t++) {
  const h = randomHistogram(1 + Math.floor(Math.random() * 60), 6);
  const { ties } = solveChecked(h);   // throws if non-decreasing ever breaks
  checked++;
  if (ties > 0) tiedStacks++;
}
console.log(`${checked} histograms, non-decreasing never broke`);
console.log(`inputs whose stack held two equal heights at once: ${tiedStacks}`);
console.log(`[3,3,3,3] ->`, solveChecked([3, 3, 3, 3]));

One run, node v22.23.2, lengths 1 to 60 and heights 0 to 5 so ties are frequent:

50000 histograms, non-decreasing never broke
inputs whose stack held two equal heights at once: 45502
[3,3,3,3] -> { maxArea: 12, ties: 3 }

Zero failures of the real invariant. Ties on 45,502 of 50,000 inputs, each one a counterexample to the strict version. If you swap the assertion to > the harness throws on the first input with a repeated height.

What a pop knows about the left edge

The strict wording implies something specific about a pop: that the bar directly beneath the popped one is shorter, so the popped rectangle extends left as far as it possibly can. With ties allowed, the bar beneath can be the same height, and the rectangle reported at that pop is narrower than the bar's real reach.

So measure it. trueExtent walks outward from a bar to find how wide a rectangle of that height could actually be, and auditWidths compares every pop's computed width against it.

const trueExtent = (heights, j) => {
  let l = j, r = j;
  while (l - 1 >= 0 && heights[l - 1] >= heights[j]) l--;
  while (r + 1 < heights.length && heights[r + 1] >= heights[j]) r++;
  return r - l + 1;
};
 
const auditWidths = (heights, tally) => {
  const stack = [];
  let maxArea = 0;
 
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
 
    while (stack.length > 0 && heights[stack[stack.length - 1]] > h) {
      const j = stack.pop();
      const left = stack.length > 0 ? stack[stack.length - 1] : -1;
      const width = i - left - 1;
      const real = trueExtent(heights, j);
 
      if (width === real) tally.exact++;
      else if (width < real) tally.short++;
      else tally.over++;
 
      maxArea = Math.max(maxArea, heights[j] * width);
    }
 
    stack.push(i);
  }
 
  return maxArea;
};
 
const bruteArea = (heights) => {
  let best = 0;
  for (let l = 0; l < heights.length; l++) {
    let minH = Infinity;
    for (let r = l; r < heights.length; r++) {
      minH = Math.min(minH, heights[r]);
      best = Math.max(best, minH * (r - l + 1));
    }
  }
  return best;
};
 
const tally = { exact: 0, short: 0, over: 0 };
let inputs = 0;
 
for (let len = 1; len <= 6; len++) {            // every histogram of length 1..6, heights 0..4
  for (let code = 0; code < 5 ** len; code++) {
    const h = [];
    let x = code;
    for (let k = 0; k < len; k++) { h.push(x % 5); x = Math.floor(x / 5); }
    assert(auditWidths(h, tally) === bruteArea(h), `wrong answer on ${h}`);
    inputs++;
  }
}
for (let t = 0; t < 20000; t++) {
  const h = randomHistogram(1 + Math.floor(Math.random() * 40), 5);
  assert(auditWidths(h, tally) === bruteArea(h), `wrong answer on ${h}`);
  inputs++;
}
console.log(`${inputs} histograms, all answers match brute force`);
console.log('widths', tally);

39530 histograms, all answers match brute force
widths { exact: 300626, short: 116372, over: 0 }

One run: 116,372 pops out of 417,000 — a bit over a quarter — computed a width smaller than the bar could have had. The random half of the corpus moves that count by a few hundred between runs; the over column does not move. Not one pop in the whole run overstated. The exhaustive part of that corpus covers every histogram of length 1 through 6 with heights 0 through 4, so the zero in the over column is not a sampling accident on those shapes.

Why the answer survives

Take [3, 3, 3]. All three bars are pushed, nothing pops until the sentinel, and then they come off right to left: index 2 with the new top at index 1, width 1; index 1 with the new top at index 0, width 2; index 0 with an empty stack, width 3, area 9. Two of the three pops under-report. The last one — the leftmost member of the plateau — gets the empty stack and the full width.

That generalises. Within any run of equal heights, the leftmost bar is popped last, and by then every other member of the run is gone, so its left boundary is a genuinely shorter bar. The pops that under-report are all shadowed by one that does not. Combine that with the over: 0 column and you have the argument: every reported rectangle is real, and the best real rectangle is reported.

The cost of maintaining the invariant

The inner while makes the loop look quadratic. The usual rebuttal is "each index is pushed and popped at most once", which is close: each index is pushed exactly once, including the sentinel, so pushes are bounded by n + 1, and pops by n, since you cannot pop what was never pushed.

const countOps = (heights) => {
  const stack = [];
  let pushes = 0, pops = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length > 0 && heights[stack[stack.length - 1]] > h) { stack.pop(); pops++; }
    stack.push(i); pushes++;
  }
  return { pushes, pops };
};
 
let worst = 0, totalPush = 0, totalPop = 0, totalN = 0;
for (let t = 0; t < 50000; t++) {
  const n = 1 + Math.floor(Math.random() * 60);
  const h = randomHistogram(n, 6);
  const { pushes, pops } = countOps(h);
  assert(pushes <= n + 1, `too many pushes on ${h}`);
  assert(pops <= n, `too many pops on ${h}`);
  totalPush += pushes; totalPop += pops; totalN += n;
  worst = Math.max(worst, (pushes + pops) / n);
}
console.log(`total n=${totalN} pushes=${totalPush} pops=${totalPop}`);
console.log(`worst (pushes+pops)/n = ${worst.toFixed(2)}`);
 
const timeIt = (fn, arg, reps) => {
  fn(arg); fn(arg);
  const t0 = process.hrtime.bigint();
  for (let i = 0; i < reps; i++) fn(arg);
  return Number(process.hrtime.bigint() - t0) / 1e6 / reps;
};
for (const n of [250000, 500000, 1000000, 2000000, 4000000]) {
  console.log(`n=${n}  ${timeIt(largestRectangleArea, randomHistogram(n, 100000), 5).toFixed(1)} ms`);
}

total n=1524190 pushes=1574190 pops=1269734
worst (pushes+pops)/n = 3.00
n=250000  3.4 ms
n=500000  6.8 ms
n=1000000  12.6 ms
n=2000000  25.1 ms
n=4000000  50.5 ms

Both asserts held on all 50,000 inputs. The worst ratio of 3.00 comes from single-bar inputs, where n is 1 and the sentinel adds a push. On the timings, each doubling of n roughly doubles the time — 3.4 to 6.8 to 12.6 to 25.1 to 50.5. The bruteArea above, on the same machine, took 3.0 ms at n = 2,000 and 186.3 ms at n = 16,000: an eightfold increase in n for a sixtyfold increase in time, which is the quadratic shape.

The linear shape depends on the stack being a stack. Swapping stack.pop() for stack.shift() or hunting for the left boundary with indexOf puts an O(n) operation inside the loop and the curve stops doubling. Rerun timeIt after any change to those lines.

Maximal Rectangle reuses the same stack

LeetCode 85 asks for the largest all-'1' rectangle in a binary matrix. Process the matrix row by row, keeping a per-column count of consecutive '1's ending at that row. Each row's counts are a histogram, and its largest rectangle is a rectangle of '1's whose bottom edge is that row. Every rectangle in the matrix has a bottom edge somewhere, so every one of them gets considered.

const maximalRectangle = (matrix) => {
  if (matrix.length === 0 || matrix[0].length === 0) return 0;
  const heights = new Array(matrix[0].length).fill(0);
  let maxArea = 0;
 
  for (const row of matrix) {
    for (let col = 0; col < row.length; col++) {
      heights[col] = row[col] === '1' ? heights[col] + 1 : 0;
    }
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }
 
  return maxArea;
};
 
const bruteMaximal = (matrix) => {
  const m = matrix.length;
  if (m === 0) return 0;
  const n = matrix[0].length;
  let best = 0;
  for (let r1 = 0; r1 < m; r1++) for (let c1 = 0; c1 < n; c1++)
    for (let r2 = r1; r2 < m; r2++) for (let c2 = c1; c2 < n; c2++) {
      let ok = true;
      for (let r = r1; r <= r2 && ok; r++) for (let c = c1; c <= c2; c++)
        if (matrix[r][c] !== '1') { ok = false; break; }
      if (ok) best = Math.max(best, (r2 - r1 + 1) * (c2 - c1 + 1));
    }
  return best;
};
 
let matrices = 0;
for (let m = 1; m <= 3; m++) for (let n = 1; n <= 4; n++) {
  for (let bits = 0; bits < 1 << (m * n); bits++) {
    const matrix = Array.from({ length: m }, (_, r) =>
      Array.from({ length: n }, (_, c) => ((bits >> (r * n + c)) & 1) ? '1' : '0'));
    assert(maximalRectangle(matrix) === bruteMaximal(matrix), `wrong on ${JSON.stringify(matrix)}`);
    matrices++;
  }
}
console.log(`${matrices} binary matrices up to 3x4, all match brute force`);
console.log('degenerate:', [[], [[]], [['0','0'],['0','0']], [['1','1','0','1']], [['1'],['1'],['0'],['1']]]
  .map(maximalRectangle));

5050 binary matrices up to 3x4, all match brute force
degenerate: [ 0, 0, 0, 2, 2 ]

Every binary matrix up to three rows by four columns, checked against a brute force over all submatrices. The degenerate line covers an empty matrix, a matrix with an empty row, all zeros, a single row, and a single column. The matrix[0].length === 0 half of the guard is what keeps [[]] from reaching the solver with a zero-width histogram.

Note that heights is one array, mutated in place and handed to largestRectangleArea on every row. That works only because the solver reads heights and never writes to it. It is also why the cells are compared with === '1' rather than === 1 — the matrix holds characters.

The invariant is not the proof

One inconvenient result. Change the pop test from > to >= and the stack really does become strictly increasing — ties get popped on sight. Run that version against bruteArea over the same 39,530-input corpus and it also gets every answer right. Enforcing the stronger invariant changes which pop reports the winning rectangle, and changes nothing about the returned number.

So the invariant on its own does not explain correctness, and an article that stops at "the stack is increasing" has stopped one step early. What carries the proof is the pair of properties around it: no pop ever overstates a width, and for every candidate rectangle some pop measures it exactly. The monotone stack is the mechanism that makes both cheap to guarantee, and it is worth stating carefully. Treat it as the reason the answer is right and you will be unable to say why the >= version is right too — which is the version half your teammates will write from memory.