Stack • Monotonic Stack

Largest Rectangle in Histogram

Given an array of integer heights representing a histogram, find the area of the largest bounding rectangle.

The Core Insight

For any bar, the largest rectangle that fully includes it is limited by the first strictly smaller bar to its left, and the first strictly smaller bar to its right.

Monotonic Stack

We use a stack to keep track of bars in strictly increasing height order. When we see a smaller bar, it acts as the "right boundary" for the taller bars currently sitting on top of the stack.

Calculating Width

When popping a bar, its height `h` is known. Its right boundary is the current index `i`. Its left boundary is the index of whatever remains at the top of the stack after it's popped!

2

1

5

6

2

3

Stack (Indices)

Max Area

0

Code Tracker

:::

1let stack = [], maxArea = 0;

2for (let i = 0; i <= n; i++) {

3 while (stack.length && (i === n || heights[stack[stack.length-1]] > heights[i])) {

4 let h = heights[stack.pop()];

5 let w = stack.length === 0 ? i : i - stack[stack.length-1] - 1;

6 maxArea = Math.max(maxArea, h * w);

7 }

8 stack.push(i);

9}

10return maxArea;

Largest Rectangle Histogram

Largest Rectangle Histogram

Largest Rectangle in Histogram

The Core Insight

Monotonic Stack

Calculating Width

Largest Rectangle in Histogram

The Core Insight

Monotonic Stack

Calculating Width