Largest Rectangle in Histogram

STACK · HARD

The problem

You’re given an array heights, where each element is the height of one bar in a histogram — every bar has width 1 and they sit side by side with no gaps. Find the area of the largest rectangle that fits entirely inside the histogram’s outline. The rectangle’s width can span any contiguous run of bars, but its height is capped by the shortest bar in that run — a taller bar can’t poke out above the rectangle’s top edge.

Example: heights = [2,1,5,6,2,3] → 10. That comes from bars at indices 2 and 3 (heights 5 and 6): the shorter of the two, height 5, limits the rectangle, and a width-2 run at height 5 gives area 5 × 2 = 10 — bigger than any single bar alone, and bigger than any wider-but-shorter run.

LeetCode: Largest Rectangle in Histogram

Solution 1: Brute force — expand outward from every bar

Every valid rectangle in this problem is limited by some bar — the shortest one in its span. So a direct way to search is: for every bar i, treat heights[i] as if it were the limiting height, and find the widest possible run centered on i where every bar is at least that tall. Expand a left pointer leftward and a right pointer rightward from i while the neighboring bars are >= heights[i] — the moment a shorter bar is hit in either direction, that boundary is fixed, because a shorter bar would violate “every bar in this run is at least heights[i] tall.” The resulting width times heights[i] is a candidate area; the largest one across all i is the answer.

heights = [2, 1, 5, 6, 2, 3] — brute force expands per bar

Press Play or Step to begin.

Step 0 / 8

The code

function largestRectangleBrute(heights) {
  const n = heights.length;
  let best = 0;

  for (let i = 0; i < n; i++) {
    let left = i;
    while (left - 1 >= 0 && heights[left - 1] >= heights[i]) left--;

    let right = i;
    while (right + 1 < n && heights[right + 1] >= heights[i]) right++;

    const width = right - left + 1;
    const area = width * heights[i];
    if (area > best) best = area;
  }
  return best;
}

Line by line:

best starts at 0 — heights are non-negative, so an empty/no rectangle answer of 0 is a safe floor.
The first while walks left down from i as long as the bar just to its left is still >= heights[i] — the loop condition also guards left - 1 >= 0 so it never reads past the start of the array.
The second while does the mirror image on right, using >= heights[i] again — both directions use the same “still tall enough” test, since either side could be the one that ends the run.
width = right - left + 1 counts every bar from left to right inclusive; area = width * heights[i] is the candidate rectangle with heights[i] as its limiting height.
Every bar gets its own independent expansion — that’s what guarantees the true widest run for each possible limiting height gets checked somewhere in the loop.

Complexity

Time	Space	Approach
O(n²)	O(1)	Every bar expands outward independently; worst case (sorted input) walks the full array each time

Solution 2: Optimal — monotonic increasing stack

The brute force re-derives, from scratch, “how far can this bar’s height reach before hitting something shorter?” — for every single bar. A monotonic stack answers that question for many bars at once, in a single left-to-right pass. Keep a stack of indices whose heights are in strictly increasing order (bottom to top). At each new bar i: while the bar on top of the stack is taller than heights[i], that’s the signal that bar’s run has just been closed off on the right — pop it and compute its rectangle right then. Its right boundary is i - 1 (it can’t extend into i, since heights[i] is shorter); its left boundary is one past whatever index is now on top of the stack (or the very start of the array, if the stack is now empty) — because that remaining stack entry is the nearest bar to the left that’s still shorter than the bar being popped. After all the necessary pops, push i — the stack stays increasing by construction. Once the scan finishes, anything still left on the stack never found a shorter bar to its right, so it’s drained the same way, using the end of the array as the right boundary.

heights = [2, 1, 5, 6, 2, 3] — monotonic increasing stack, O(n)

Press Play or Step to begin.

Step 0 / 14

The code

function largestRectangleOptimal(heights) {
  const n = heights.length;
  const stack = []; // indices, heights strictly increasing bottom to top
  let best = 0;

  for (let i = 0; i < n; i++) {
    while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
      const topIdx = stack.pop();
      const height = heights[topIdx];
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }

  while (stack.length) {
    const topIdx = stack.pop();
    const height = heights[topIdx];
    const width = stack.length ? n - stack[stack.length - 1] - 1 : n;
    best = Math.max(best, height * width);
  }

  return best;
}

Line by line:

The stack holds indices, not heights — the height is always recovered via heights[topIdx], so the boundary index is available for the width math.
while (stack.length && heights[stack[stack.length - 1]] > heights[i]): this is strictly greater-than, not >= — equal-height bars are allowed to sit together on the stack, since a bar of the same height never actually closes off another bar’s run.
width = stack.length ? i - stack[stack.length - 1] - 1 : i is the classic off-by-one spot. The popped bar’s right boundary is i - 1 (it stops one short of i, which is shorter). Its left boundary is stack[top] + 1 if the stack still has an entry after the pop, or 0 if it’s now empty. Both cases collapse to the same one-line formula: subtract the (now-exclusive) left boundary index from i — when the stack is empty that boundary is effectively -1, so i - (-1) - 1 simplifies to just i.
stack.push(i) runs after every pop is finished — by then everything left on the stack (if anything) is strictly shorter than heights[i], so pushing i keeps the increasing order intact.
The second while after the main loop drains anything left on the stack — those bars never met a shorter bar to their right during the scan, so their right boundary is the actual end of the array, n (or n - 1 inclusive), handled with the exact same width formula, just swapping i for n.

Complexity

Time	Space	Approach
O(n)	O(n)	Monotonic increasing stack — every index pushed once, popped at most once, over the whole scan

The inner while loop looks like it could make this quadratic, the same shape as a nested loop — but it isn’t one. Every index gets pushed onto the stack exactly once, and once popped, it is gone for good; it never gets pushed again. That means across the entire run of the algorithm — the whole outer for loop plus the final drain — the total number of pops can never exceed the total number of pushes, which is n. So even though any single iteration of the outer loop might trigger several pops in a row, the pops are “paid for” by earlier pushes that haven’t been charged yet — summed over the whole run, the while loops together do at most n units of work, not n per iteration. This is the same amortized-cost argument used to show that a dynamic array’s occasional resizing doesn’t make individual push calls slow.

Complexity comparison

Solution	Time	Space
Brute force (expand outward per bar)	O(n²)	O(1)
Optimal (monotonic increasing stack)	O(n)	O(n)

This is a genuine asymptotic time improvement, not a constant-factor tweak — the monotonic stack replaces “re-derive each bar’s reach from scratch” with “resolve each bar’s right boundary the moment a shorter bar appears,” which an amortized argument shows costs O(n) total rather than O(n) per bar. The trade is real, not free, though: the optimal solution spends O(n) extra space on the stack, where the brute force needed none.

Interview corner

Why does expanding left/right while neighbors are >= heights[i] correctly find the widest run where heights[i] is the limiting height?

“heights[i] is the limiting height of this run” means every bar in the run must be tall enough to support a rectangle of that height — i.e. every bar must be >= heights[i].
The expansion stops the instant a shorter bar is hit in either direction, because that shorter bar cannot be part of a run limited by heights[i] — including it would make heights[i] no longer the true minimum of the run.
Since the expansion greedily includes every neighbor that still qualifies and stops the moment one doesn’t, the resulting [left, right] window is exactly the widest such run — not an approximation of it.

The optimal solution’s inner while loop is nested inside the outer for loop — why is the total cost still O(n) and not O(n²)?

Every index enters the stack via push exactly once, ever — there’s no code path that pushes the same index twice.
Once an index is popped, it’s permanently gone — it’s never re-pushed later, so it can never be popped a second time either.
That means, summed across the entire algorithm (not per iteration), the number of pop operations is capped at n, the same as the number of pushes — so the combined work of every while loop execution, added up, is O(n), even though it’s not evenly spread one-per-iteration.

Why does the width formula switch between i - stack[stack.length - 1] - 1 and plain i depending on whether the stack is empty after the pop?

The popped bar’s left boundary is defined by the next shorter bar to its left — whatever is now on top of the stack, one position past it.
If the stack is empty after the pop, there is no shorter bar anywhere to the left — meaning the popped bar’s run extends all the way back to index 0, making the width simply i (everything from 0 to i - 1).
Both branches are really the same formula in disguise: treat an empty stack as if its “top” were at index -1, and i - (-1) - 1 reduces to i — the if/else just avoids reading stack[-1], which in JavaScript would silently return undefined rather than throw.

Trick question — what does this log?

const stack = [];
console.log(stack.pop());
console.log(stack.length);

Answer: undefined, then 0 — not a thrown error.
Array.prototype.pop() on an empty array doesn’t throw; it silently returns undefined and leaves the array unchanged (still length 0).
The optimal solution above guards every pop with while (stack.length && ...) — that guard isn’t just style. Without it, an empty-stack pop would hand back undefined as an “index,” and heights[undefined] is itself undefined, which would silently turn the area calculation into NaN instead of crashing — a much harder bug to notice than a thrown error.

Quiz

1. In the brute-force solution, what does the expansion around bar i actually find?

The single tallest bar anywhere in the whole array
The widest contiguous run where every bar is at least as tall as heights[i], so heights[i] is the limiting height
A sorted copy of the neighboring bars around index i

Explanation

For each bar i, the brute force expands left and right while neighboring bars are still >= heights[i], finding the widest run where heights[i] is the shortest (limiting) bar, then multiplies that width by heights[i].

2. Why does the optimal solution’s pop condition use strict > (heights[stack.top] > heights[i]) instead of >=?

It’s purely a micro-optimization with no effect on the computed answer
JavaScript’s array comparison operators don’t support >= between numbers
Equal-height bars don’t close off each other’s runs, so they’re allowed to coexist on the stack rather than triggering a pop

Explanation

The while loop pops only while the stack top is STRICTLY taller than heights[i] (>, not >=). Bars of equal height are allowed to coexist on the stack, since an equal-height bar never actually closes off another bar’s run — the rectangle at that height could still extend across both.

3. What specifically makes the optimal solution O(n) despite the inner while loop nested inside the outer for loop?

It’s only tested on a small 6-element array, not a real complexity guarantee
The while loop is skipped entirely whenever the array is already sorted
Each index is pushed exactly once and popped at most once across the entire run, so total pop work is bounded by n, not n per iteration

Explanation

Every index is pushed onto the stack exactly once and, once popped, is never pushed again. Summed across the whole algorithm (not per iteration), total pops can never exceed n, the total number of pushes — so the combined cost of every while-loop execution is O(n), not O(n) per outer iteration.

4. After popping a bar from the stack, why is the new stack top (if any) exactly the popped bar’s left boundary marker?

It’s an arbitrary choice — any remaining stack entry would work equally well
It’s always index 0, regardless of what’s left on the stack
Because the stack is increasing, whatever remains on top is the nearest bar to the left that’s still shorter than the popped bar — the natural left edge of its run

Explanation

A popped bar’s left boundary is the nearest bar to its left that’s still shorter than it — exactly whatever index remains on top of the stack after the pop (one position past it). If the stack is empty, no such bar exists anywhere to the left, so the run reaches back to index 0.

5. Why does the optimal solution need a second drain loop after the main for loop finishes?

It’s just memory cleanup with no effect on the computed answer
It’s redundant — the main loop already prices every bar correctly on its own
Anything still on the stack never met a shorter bar to its right during the scan, so its rectangle hasn’t been priced yet and needs n as its right boundary

Explanation

Any index still on the stack once the main scan finishes never encountered a shorter bar anywhere to its right during the whole array — meaning its run extends all the way to the actual end of the array, so it needs to be priced using n as the right boundary instead of some i from the loop.