Largest Rectangle in Histogram - Three Solutions with Interactive Visualization

Problem Statement (LC 84)

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
The largest rectangle spans bars with heights 5 and 6, with height 5 and width 2.

Example 2:

Input: heights = [2,4]
Output: 4

Key Insight

The Height Must Be From the Array

The maximum rectangle’s height must be one of the values in heights. Why?

If we pick a height that’s NOT in the array (say height 4), we could always increase it until we hit some bar’s top, getting a larger rectangle. Contradiction!

The crucial reframing: fix the height (treat bar `i` as the limiting height)

For every index i, treat heights[i] as the rectangle’s limiting (minimum) height. Then the rectangle can expand left/right until it hits a bar that is strictly smaller.

left[i] = index of the first bar on the left with height < heights[i] (or -1 if none)
right[i] = index of the first bar on the right with height < heights[i] (or n if none)
width = right[i] - left[i] - 1
area = heights[i] * width

What We Need for Each Bar

For each bar at index i with height h = heights[i], if we use it as the rectangle’s height, we need:

Left boundary: The index of the first bar shorter than h to the left (or -1 if none)
Right boundary: The index of the first bar shorter than h to the right (or n if none)

Then: width = right[i] - left[i] - 1, area = h × width

Why “First Shorter”?

Consider: if we don’t find the nearest shorter bar but some farther one, we’d include bars we shouldn’t. The rectangle would extend beyond the valid region.

Example: heights = [2, 1, 5, 6, 2, 3]

For bar at index 2 (height 5):
- Left boundary: index 1 (height 1 < 5)  ✓
- Right boundary: index 4 (height 2 < 5) ✓
- Width = 4 - 1 - 1 = 2
- Area = 5 × 2 = 10

Solution 1: Three-Pass (Most Intuitive)

The most straightforward approach: use monotonic stack separately for left and right boundaries.

What’s in the stack? What invariant do we maintain?

We store indices, not heights (so width is easy to compute)
From bottom to top, the heights are strictly increasing:

heights[stack[0]] < heights[stack[1]] < ... < heights[stack[top]]

This means: the stack top is the rightmost “small height candidate” so far. When we see a smaller (or equal) bar, taller bars can no longer extend to the right, so their boundary information becomes determined.

Algorithm

Pass 1 (left to right): For each bar, find left[i] = index of first shorter bar on left
Pass 2 (right to left): For each bar, find right[i] = index of first shorter bar on right
Pass 3: Calculate area for each bar, track maximum

Why Monotonic Stack Works

A monotonic increasing stack helps us find “next smaller” elements efficiently:

When processing heights[i], we pop all indices with height ≥ heights[i]
- those bars can’t be “the first shorter” for i
- it also avoids double-counting when heights are equal
After popping, the remaining stack top (if any) is the nearest index with height < heights[i], i.e. left[i]

Walkthrough

heights = [2, 1, 5, 6, 2, 3]

Pass 1 (find left[]):
i=0: stack empty → left[0]=-1, push 0
i=1: heights[0]=2 > 1 → pop 0, stack empty → left[1]=-1, push 1
i=2: heights[1]=1 < 5 → left[2]=1, push 2
i=3: heights[2]=5 < 6 → left[3]=2, push 3
i=4: pop 3,2 (both >= 2) → left[4]=1, push 4
i=5: heights[4]=2 < 3 → left[5]=4, push 5

left = [-1, -1, 1, 2, 1, 4]

Pass 2 (find right[]):
i=5: stack empty → right[5]=6, push 5
i=4: heights[5]=3 > 2 → pop 5, stack empty → right[4]=6, push 4
i=3: heights[4]=2 < 6 → right[3]=4, push 3
i=2: heights[3]=6 > 5 → pop 3, heights[4]=2 < 5 → right[2]=4, push 2
i=1: pop 2,4 → right[1]=6, push 1
i=0: heights[1]=1 < 2 → right[0]=1, push 0

right = [1, 6, 4, 4, 6, 6]

Pass 3 (calculate areas):
i=0: 2 × (1-(-1)-1) = 2 × 1 = 2
i=1: 1 × (6-(-1)-1) = 1 × 6 = 6
i=2: 5 × (4-1-1) = 5 × 2 = 10  ← maximum!
i=3: 6 × (4-2-1) = 6 × 1 = 6
i=4: 2 × (6-1-1) = 2 × 4 = 8
i=5: 3 × (6-4-1) = 3 × 1 = 3

Solution 2: Two-Pass (Optimized)

Goal: compute both left[] and right[] in a single left-to-right scan, then do one more pass to compute areas.

Key observation: why is `right[popped] = i` when we pop?

When scanning index i with current height h = heights[i]:

if the stack top j satisfies heights[j] ≥ h, we pop j
the moment j is popped, we have found the first position to the right of j whose height is ≤ heights[j]
because the stack maintains increasing heights, j cannot extend past i anymore

So we can assign immediately: right[j] = i.

For the current index i:

after popping all ≥ h, the remaining stack top (if any) is left[i]
then push i

Handling Duplicates

Why do we use >= instead of > in the pop condition?

Benefit: equal-height bars “merge” into the rightmost representative, avoiding duplicated width/area candidates
Note: this makes right[] behave like “first position with height ≤ current height” rather than strictly <. The final max area remains correct because at least one representative will capture the maximal width for that plateau.

Walk through the same example (focus on the pops)

heights = [2, 1, 5, 6, 2, 3]
init: left = [-1...], right = [n...], stack = []

i=0,h=2: stack empty → left[0]=-1, push 0
i=1,h=1: heights[0]=2 >= 1 → pop 0, set right[0]=1
          stack empty → left[1]=-1, push 1
i=2,h=5: heights[1]=1 < 5 → left[2]=1, push 2
i=3,h=6: heights[2]=5 < 6 → left[3]=2, push 3
i=4,h=2: heights[3]=6 >= 2 → pop 3, right[3]=4
          heights[2]=5 >= 2 → pop 2, right[2]=4
          heights[1]=1 < 2 → left[4]=1, push 4
i=5,h=3: heights[4]=2 < 3 → left[5]=4, push 5

left  = [-1, -1, 1, 2, 1, 4]
right = [ 1,  6, 4, 4, 6, 6]

Solution 3: One-Pass (Optimal)

The Ultimate Optimization

The previous two solutions compute boundaries first, then compute areas.

But we can avoid storing full boundary arrays: when a bar is popped, its maximal width is already fully determined, so we can compute its area right away.

Yes! When we pop an element:

Right boundary: current index (the trigger for popping)
Left boundary: the element below in the stack!

The key invariant

We still maintain an increasing-height stack (indices).

When we pop an index p while scanning i (height h):

right = i because h <= heights[p] stops p from extending further
left = stack.peek() after popping (the nearest index on the left with smaller height)

So:

area(p) = heights[p] * (right - left - 1)

Using Sentinels

To simplify edge cases:

Push -1 as the left sentinel (bottom of stack) — handles “no shorter bar on left”
Append -1 to heights as the right sentinel — ensures all elements get popped

Original: [2, 1, 5, 6, 2, 3]
With sentinels: stack starts with [-1], process heights + [-1]

Understand one-pass pops (the magic is at `i=4`)

heights = [2, 1, 5, 6, 2, 3], append -1 at end
stack starts [-1]

i=0,h=2: push 0         stack [-1,0]
i=1,h=1: pop 0:
          right=1, left=-1 → area = 2 * (1-(-1)-1)=2
          push 1         stack [-1,1]
i=2,h=5: push 2         stack [-1,1,2]
i=3,h=6: push 3         stack [-1,1,2,3]

i=4,h=2: triggers consecutive pops (6>=2, 5>=2):
  pop 3 (height=6):
    right=4, left=2 → area = 6 * (4-2-1)=6
  pop 2 (height=5):
    right=4, left=1 → area = 5 * (4-1-1)=10  ← max appears here
  then push 4           stack [-1,1,4]

When we finally reach the trailing -1, we pop the remaining bars, which is basically a “final settlement”.

The sentinel -1 at stack bottom ensures we always have a valid “left boundary” (meaning the bar can extend all the way to the left edge).

Interactive Visualization

Try different solution types to see how each approach works step by step:

Initializing...

Key Observations

Three-Pass: Easiest to understand, computes left[], right[] separately
Two-Pass: Realizes that popping gives us the right boundary immediately
One-Pass: Uses sentinels to calculate area on-the-fly during popping

Complexity Analysis

Solution	Time	Space
Three-Pass	O(n)	O(n)
Two-Pass	O(n)	O(n)
One-Pass	O(n)	O(n)

All three solutions have the same asymptotic complexity because each element is pushed and popped at most once. The one-pass solution has slightly better constants due to fewer iterations.

Space Breakdown

Stack: O(n) in worst case (ascending heights)
Arrays (left, right): O(n) for three-pass and two-pass
One-pass doesn’t need separate arrays (slight advantage)

Problem	Difficulty	Key Idea
LC 85: Maximal Rectangle	Hard	Apply LC 84 to each row
LC 42: Trapping Rain Water	Hard	Similar monotonic stack pattern
LC 739: Daily Temperatures	Medium	Next greater element
LC 496: Next Greater Element I	Easy	Basic monotonic stack

Pattern Recognition

When you see these keywords, think monotonic stack:

“First/next greater/smaller element”
“Maximum rectangle in histogram”
“Width/span until smaller/larger”
“Area calculation with boundaries”

Summary

Approach	Passes	Key Technique
Three-Pass	3	Separate left/right boundary computation
Two-Pass	2	Pop gives right boundary immediately
One-Pass	1	Sentinels + calculate on pop

The progression from three-pass to one-pass demonstrates how we can incrementally optimize by identifying what information is available at each moment. The one-pass solution is elegant but harder to derive—understanding the three-pass solution first makes the optimization path clearer.

Master this problem, and you’ll have a solid foundation for all histogram-based interview questions!