Algorithm

Largest Rectangle in Histogram

Monotonic Stack Pattern

Largest Rectangle in Histogram

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

CONSTRAINTS
  • 1 <= heights.length <= 10⁵
  • 0 <= heights[i] <= 10⁴
EXAMPLE 1
Input: heights = [2,1,5,6,2,3]
Output: 10
Bars at index 2 and 3 (heights 5, 6) form a 5x2=10 rectangle.
EXAMPLE 2
Input: heights = [4, 2, 0, 3, 2, 5]
Output: 6
Bars at indices 3, 4, 5 can form a 2x3=6 rectangle.
What is the purpose of the 0 sentinel?
It ensures that after the loop finishes, any remaining bars in the stack (bars that never found a smaller neighbor to their right) are finally popped and their areas are calculated.

Finding the area of the largest rectangle in a histogram is a challenge of boundaries. The area of any rectangle is governed by the formula:
Area = height × width

In a histogram where every bar has a width of 1, if we fix a specific bar as the "height", its maximum width is determined by how far it can expand to the left and right before hitting a bar shorter than itself.
Width = (Right Boundary - Left Boundary - 1)

The bottleneck in a naive approach is that the shortest bar in any group always dictates the height for the entire range.

Brute Force (O(N²) Time, O(1) Space)

We pick every possible pair of bars as the left and right boundaries. For every pair, we find the shortest bar between them to determine the height.

python
max_area = 0
n = len(heights)
for i in range(n):
    min_h = heights[i]
    for j in range(i, n):
        # Update minimum height for the current range
        min_h = min(min_h, heights[j])
        max_area = max(max_area, min_h * (j - i + 1))
return max_area
The Memory Trade-off (O(N) Time, O(N) Space)

To speed this up, we can use extra memory to pre-calculate the boundaries for every single bar. For each bar $i$, we want to know:
1. Left Boundary: The index of the first bar to the left that is strictly shorter than $heights[i]$.
2. Right Boundary: The index of the first bar to the right that is strictly shorter than $heights[i]$.

If we store these in two arrays, left_smaller and right_smaller, we can calculate the area for every bar in a single pass.

python
# Pre-calculate boundaries (using two passes)
# Once we have left_smaller and right_smaller:
for i in range(n):
    width = right_smaller[i] - left_smaller[i] - 1
    max_area = max(max_area, heights[i] * width)
The Monotonic Stack (O(N) Time, O(N) Space)

To optimize even further and avoid multiple passes, we use a Monotonic Stack. By maintaining a stack of indices in increasing order of height, we can resolve the boundaries of multiple bars in a single pass.

The strategy works as follows:
- The Discovery: We scan the histogram from left to right. If the current bar is shorter than the bar at the top of our stack, we have found a "Right Wall" for that top bar.
- The Calculation: We pop the top index (the height). The "Left Wall" is the new top of the stack (the nearest smaller bar to its left). The width is then calculated as the distance between these two walls.
- The Sentinel: We add a virtual bar of height 0 at the very end. This ensures that every remaining bar in the stack is forced out and its area is calculated before the process ends.

python
# Monotonic Stack (O(N) Time, O(N) Space)
heights.append(0) # Sentinel to flush the stack
stack = [-1] # Virtual left wall
max_area = 0

for i in range(len(heights)):
    # While current bar is a 'Right Wall' for the stack top
    while len(stack) > 1 and heights[i] < heights[stack[-1]]:
        h = heights[stack.pop()]
        w = i - stack[-1] - 1
        max_area = max(max_area, h * w)
    
    stack.append(i)
return max_area

By resolving each bar exactly once, we transform a nested search into a perfect linear scan. The stack acts as a memory of "unsolved" heights, waiting for their boundaries to be discovered.

Worked Example:[2, 1, 5, 6, 2, 3] (plus 0 sentinel)
0
2
Stack
1
1
2
5
3
6
4
2
5
3
6
0
Start at index 0 (h=2): Push index 0 to stack. Stack = [-1, 0] (using -1 as left boundary sentinel).
0
2
Max Area
1
1
2
5
3
6
4
2
5
3
6
0
Index 1 (h=1): 1 < 2. Pop index 0. Height = 2. Width = 1 - (-1) - 1 = 1. Area = 2 * 1 = 2. Push 1. Stack = [-1, 1].
0
2
1
1
2
5
3
6
Stack
4
2
5
3
6
0
Index 2 (h=5) & Index 3 (h=6): Both are larger than stack top. Push both. Stack = [-1, 1, 2, 3].
0
2
1
1
2
5
3
6
Max Area
4
2
5
3
6
0
Index 4 (h=2): 2 < 6. Pop index 3. Height = 6. Width = 4 - 2 - 1 = 1. Area = 6 * 1 = 6. Stack = [-1, 1, 2].
0
2
1
1
2
5
Max Area
3
6
4
2
5
3
6
0
Still index 4: 2 < 5. Pop index 2. Height = 5. Width = 4 - 1 - 1 = 2. Area = 5 * 2 = 10 (green). Push index 4. Stack = [-1, 1, 4].
0
2
1
1
2
5
3
6
4
2
5
3
6
0
Remaining indices resolved by sentinel 0. Max area recorded is 10.
Interactive Strategy Visualization
RECTILINEAR GEOMETRY ENGINE

Monotonic Stack boundary technique

2
1
5
6
2
3

Mental Model

  • The Limiter: Each bar `i` extends as long as neighboring bars are *taller*.
  • Boundary Finding: Use a Monotonic Stack to find the nearest smaller element on both sides in O(N).
LOGICSTEP 1/8
For each bar, find the largest rectangle where it is the minimum height.
HINT

O(N) Complexity

The brute force approach takes O(N²). Monotonic Stack allows us to find the best boundaries for every single bar in linear time!

O(N²) Brute Force
→
O(N) Pre-calculation
→
O(N) Monotonic Stack