You're given a histogram — an array of bar heights like [2, 1, 5, 6, 2, 3] — and asked: what's the area of the largest rectangle you can draw that fits entirely within the bars?

This is LC 84: Largest Rectangle in Histogram. It's rated Hard for a reason. The rectangle can span multiple bars, but its height is limited by the shortest bar in the span. So a tall bar flanked by shorter bars can only contribute a narrow rectangle, while a moderate-height bar with long reach to both sides might form something much larger.

The brute force is to try every pair of left and right boundaries — O(n^2) pairs — and for each pair, find the minimum height in that range. If you naively scan for the minimum, that's O(n^3). Even with a sparse table for range-minimum queries, you're still at O(n^2) for the pair enumeration.

But there's a way to do it in a single pass.

Flip the problem. Instead of trying every rectangle, focus on each bar and ask: how far can this bar extend?

For a bar of height h at position i, the largest rectangle using h as its height extends left until it hits a bar shorter than h, and extends right until it hits a bar shorter than h. The width is the distance between those two boundaries (exclusive), and the area is h * width.

If you could find the nearest shorter bar on the left and right for every position, you'd just compute height[i] * (rightBoundary[i] - leftBoundary[i] - 1) for each bar and take the maximum.

Sound familiar? “Nearest shorter element on both sides” is exactly what a monotonic stack computes. Specifically, a monotonically increasing stack (values increasing from bottom to top). When a bar gets popped because something shorter arrived, the thing that arrived is its right boundary, and the new stack top is its left boundary.

But here's the clever part: you don't even need two passes. You can compute the area at pop time in a single sweep.

Walk through the histogram bar by bar. Each bar enters the stack. When a shorter bar arrives, it triggers pops — and each popped bar reveals its boundaries in that moment.

The popped bar's height is the rectangle's height. The current bar is the right boundary. The new stack top is the left boundary. Width = rightIndex - leftIndex - 1.

Watch the rectangles form as bars get popped. Track the maximum area across all pops.

There's one subtlety the interactive might have revealed: what happens to bars that are never popped during the traversal? If the histogram is monotonically increasing — say [1, 2, 3, 4, 5] — no bar ever triggers a pop, and the stack is full at the end.

The solution is a sentinel: append a bar of height 0 at the end of the array. This fictional bar is shorter than everything, so it forces every remaining bar off the stack, guaranteeing every rectangle gets computed.

function largestRectangle(heights: number[]): number {

  const stack: number[] = [-1]; // sentinel: left boundary

  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {

    // Treat index n as height 0 (right sentinel)

    const h = i === heights.length ? 0 : heights[i];

    while (stack.length > 1 && heights[stack.at(-1)!] >= h) {

      const height = heights[stack.pop()!];

      const width = i - stack.at(-1)! - 1;

      maxArea = Math.max(maxArea, height * width);

    }

    stack.push(i);

  }

  return maxArea;

}

Notice the initial -1 in the stack — that's a left sentinel. When a bar extends all the way to the left edge, the stack top after popping is -1, making the width i - (-1) - 1 = i. Both sentinels handle edge cases that would otherwise need special-case code.

The width formula i - stack.at(-1)! - 1 is the single most important line. It measures the gap between the right boundary (current position i) and the left boundary (new stack top after the pop), exclusive on both ends. Getting this off by one is the most common mistake in implementations.

The histogram rectangle problem isn't just a standalone hard problem — it's a building block for even harder ones.

Maximal Rectangle (LC 85) asks for the largest rectangle of 1s in a binary matrix. The trick: treat each row as the base of a histogram where the bar heights are the number of consecutive 1s above that row. Then run the histogram algorithm on each row. An m x n matrix becomes m histogram problems, each O(n), for O(m * n) total.

Trapping Rain Water (LC 42) uses the same “nearest shorter on both sides” structure, though it's often solved with other techniques too.

The mental model to carry forward from this lesson: when a pop reveals two boundaries simultaneously — the incoming element on one side, the remaining stack top on the other — you can compute something about the span between them. For histograms, that's area. For rain water, that's volume. The stack doesn't just find nearest elements — it finds the gap between constraint boundaries.