Data Structures & AlgorithmsMonotonic Stacks

Monotonic Stacks — Advanced Pattern

LevelIntermediate

Duration50 mins

TopicMonotonic Stacks

4 / 4

Histogram Area and Related Problems

The Crown Jewel of Monotonic Stack Problems

If there is one problem that serves as the ultimate test of monotonic stack mastery, it's the Largest Rectangle in Histogram problem. This classic problem has appeared in countless technical interviews at top companies and is frequently cited as one of the most elegant applications of the monotonic stack pattern.

This problem is special because it combines multiple concepts:

Finding both left and right boundaries
Understanding how smaller elements limit the extent of rectangles
Efficiently computing areas in a single pass

Mastering this problem unlocks solutions to an entire family of related problems, including the famous 'Maximal Rectangle in Binary Matrix.'

What You Will Learn

By the end of this page, you will be able to: (1) solve the Largest Rectangle in Histogram problem optimally, (2) understand exactly why the monotonic stack approach works, (3) extend the solution to 2D matrices, (4) apply similar reasoning to trapping rainwater and related problems.

The Problem: Largest Rectangle in Histogram

Problem Statement (LeetCode 84):

Given an array of non-negative integers heights representing the histogram's bar heights where the width of each bar is 1, find the area of the largest rectangle that can be formed within the histogram.

Visual Example:

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

     ┌───┐
     │   │
   ┌─┤   │
   │ │   ├───┐
   │ │   │   │   ┌───┐
 ┌─┤ │   │   ├───┤   │
 │ │ │   │   │   │   │
─┴─┴─┴───┴───┴───┴───┴─
  2 1   5   6   2   3

Answer: 10

The largest rectangle has height 5 and width 2 (covering indices 2 and 3 with heights 5 and 6, where the limiting height is 5).

     ┌───┬───┐
     │███│███│
   ┌─┤███│███│
   │ │███│███├───┐
   │ │███│███│   │   ┌───┐
 ┌─┤ │███│███│   ├───┤   │
 │ │ │███│███│   │   │   │
─┴─┴─┴───┴───┴───┴───┴───┴─
  2 1   5   6   2   3

The Core Insight

For any bar to be part of a rectangle, the rectangle's height is limited by that bar's height. The question becomes: how far left and right can a rectangle extend while maintaining at least this height? The answer: until we hit a bar shorter than the current bar.

Brute Force: Understanding the Structure

Before diving into the optimal solution, let's understand the structure through brute force:

Approach 1: Try All Pairs (O(n²) or O(n³))

For each pair of indices (i, j), the maximum rectangle is:

Width = j - i + 1
Height = minimum height between i and j
Area = width × height

This requires O(n²) pairs and O(n) to find minimum in each pair → O(n³).

With prefix minimum optimization → O(n²).

Approach 2: Expand from Each Bar (O(n²))

For each bar i, treat it as the limiting height and expand:

Find the leftmost bar ≥ heights[i]
Find the rightmost bar ≥ heights[i]
Width = right - left + 1
Area = heights[i] × width

histogram-brute.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Brute Force: O(n²)
 * For each bar, expand left and right while height >= current
 */
function largestRectangleBrute(heights: number[]): number {
    const n = heights.length;
    let maxArea = 0;
    
    for (let i = 0; i < n; i++) {
        const h = heights[i];
        
        // Find left boundary: first bar to left that is shorter
        let left = i;
        while (left > 0 && heights[left - 1] >= h) {
            left--;
        }
        
        // Find right boundary: first bar to right that is shorter
        let right = i;
        while (right < n - 1 && heights[right + 1] >= h) {
            right++;
        }
        
        // Calculate area with current bar as the limiting height
        const width = right - left + 1;
        const area = h * width;
        maxArea = Math.max(maxArea, area);
    }
    
    return maxArea;
}
 
// For [2, 1, 5, 6, 2, 3]:
// Bar 0 (h=2): left=0, right=0 (bar 1 has h=1 < 2), area = 2×1 = 2
// Bar 1 (h=1): left=0, right=5 (all bars ≥ 1), area = 1×6 = 6
// Bar 2 (h=5): left=2, right=3 (bar 4 has h=2 < 5), area = 5×2 = 10
// Bar 3 (h=6): left=3, right=3 (bar 2 has h=5 < 6), area = 6×1 = 6
// Bar 4 (h=2): left=2, right=5 (bar 1 has h=1 < 2), area = 2×4 = 8
// Bar 5 (h=3): left=5, right=5 (bar 4 has h=2 < 3), area = 3×1 = 3
// Maximum = 10

Key Observation:

The left boundary is the first shorter bar to the left (i.e., Previous Smaller Element). The right boundary is the first shorter bar to the right (i.e., Next Smaller Element).

This is exactly what a monotonically increasing stack computes efficiently!

The Optimal Monotonic Stack Solution

We use a monotonically increasing stack to find both the Next Smaller Element (right boundary) and Previous Smaller Element (left boundary) in a single pass.

Algorithm:

Maintain an increasing stack of indices
When we encounter a bar shorter than the stack top, the current bar is the right boundary for the top
The element below the top in the stack is the left boundary for the top
Pop the top and calculate its area
Continue until the stack is empty or the current bar is no longer shorter
Push the current index

histogram-optimal.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Optimal Solution: O(n) time, O(n) space
 * Monotonically increasing stack
 */
function largestRectangleInHistogram(heights: number[]): number {
    const n = heights.length;
    const stack: number[] = [];  // Stack of indices
    let maxArea = 0;
    
    // Process all bars, then handle remaining stack
    for (let i = 0; i <= n; i++) {
        // Treat index n as having height 0 (sentinel to flush the stack)
        const currentHeight = i < n ? heights[i] : 0;
        
        // While stack is not empty and current height is less than stack top
        while (stack.length > 0 && currentHeight < heights[stack[stack.length - 1]]) {
            // Pop the index whose right boundary we've found
            const poppedIndex = stack.pop()!;
            const h = heights[poppedIndex];
            
            // Left boundary: position after the new stack top (or 0 if stack empty)
            // Right boundary: i - 1 (current position - 1)
            // Width = right - left + 1 = (i - 1) - left + 1 = i - left
            //       = i - (stack.top() + 1) = i - stack.top() - 1  [if stack not empty]
            //       = i - 0 = i  [if stack empty, left boundary is 0]
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            
            const area = h * width;
            maxArea = Math.max(maxArea, area);
        }
        
        stack.push(i);
    }
    
    return maxArea;
}

Detailed Trace for [2, 1, 5, 6, 2, 3]:

Step-by-Step Trace
i	height[i]	Stack Before	Actions	Stack After	maxArea
0	2	[]	Push 0	[0]	0
1	1	[0]	1 < 2: Pop 0, h=2, w=1, area=2; Push 1	[1]	2
2	5	[1]	5 > 1: Push 2	[1, 2]	2
3	6	[1, 2]	6 > 5: Push 3	[1, 2, 3]	2
4	2	[1, 2, 3]	2 < 6: Pop 3, h=6, w=4-2-1=1, area=6; 2 < 5: Pop 2, h=5, w=4-1-1=2, area=10; Push 4	[1, 4]	10
5	3	[1, 4]	3 > 2: Push 5	[1, 4, 5]	10
6	0 (sentinel)	[1, 4, 5]	0 < 3: Pop 5, h=3, w=6-4-1=1, area=3; 0 < 2: Pop 4, h=2, w=6-1-1=4, area=8; 0 < 1: Pop 1, h=1, w=6, area=6	[]	10

The Sentinel Trick

By processing index n with height 0, we ensure all remaining elements are popped from the stack. This sentinel is shorter than any valid height, so it forces the stack to flush completely. Without this, we'd need a separate loop to process remaining elements.

Understanding the Width Calculation

The width calculation is often the trickiest part. Let's break it down precisely.

When we pop index p because of current index i:

Right boundary: i - 1 (the bar at i is shorter, so we can only extend to i - 1)
Left boundary: stack.top() + 1 after popping (the bar below p in the stack is the previous smaller element, so we can only extend from stack.top() + 1)

If stack is empty after popping, there's no shorter bar to the left, so left boundary is 0.

Width formula:

if stack is empty:
    width = i  // From 0 to i-1, that's i bars
else:
    width = i - stack.top() - 1  // From stack.top()+1 to i-1

width-visualization.pseudo

Visualization

// Example: heights = [1, 5, 4, 3, 2]
// When processing i=4 (height 2):
// Stack = [0, 1, 2, 3] (heights: 1, 5, 4, 3)
 
// Pop index 3 (height 3):
//   Right boundary = i - 1 = 3
//   Stack now = [0, 1, 2], top = 2
//   Left boundary = stack.top() + 1 = 2 + 1 = 3
//   Hmm, left = right = 3, width = 1
//   Area = 3 × 1 = 3
 
// Pop index 2 (height 4):
//   Right boundary = i - 1 = 3
//   Stack now = [0, 1], top = 1
//   Left boundary = stack.top() + 1 = 1 + 1 = 2
//   Width = 3 - 2 + 1 = 2  or  i - stack.top() - 1 = 4 - 1 - 1 = 2
//   Area = 4 × 2 = 8
 
// Pop index 1 (height 5):
//   Right boundary = i - 1 = 3
//   Stack now = [0], top = 0
//   Left boundary = stack.top() + 1 = 0 + 1 = 1
//   Width = 3 - 1 + 1 = 3  or  i - stack.top() - 1 = 4 - 0 - 1 = 3
//   Area = 5 × 3 = 15
 
// Height 2 at index 4 doesn't pop height 1 at index 0
// Push index 4
 
// Later, sentinel at index 5 pops remaining:
// Pop index 4 (height 2):
//   Stack = [0], width = 5 - 0 - 1 = 4
//   Area = 2 × 4 = 8
 
// Pop index 0 (height 1):
//   Stack = [], width = 5 (all bars)
//   Area = 1 × 5 = 5
 
// Maximum area = 15

Why This Formula Works

The stack maintains indices in increasing height order. When we pop index p, everything from stack.top()+1 to i-1 must have height ≥ heights[p] (otherwise they would have caused a pop earlier). So the rectangle with height heights[p] can safely extend over this entire range.

Alternative: Pre-compute Boundaries

Some find the single-pass solution hard to reason about. An alternative is to explicitly pre-compute the left and right boundaries using two separate passes, then compute areas in a third pass.

This is slightly less elegant but easier to understand and debug.

histogram-precompute.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Alternative: Pre-compute boundaries explicitly
 * Still O(n) time, O(n) space, but clearer logic
 */
function largestRectanglePrecompute(heights: number[]): number {
    const n = heights.length;
    
    // leftBound[i] = index of previous smaller element, or -1 if none
    const leftBound = new Array(n).fill(-1);
    // rightBound[i] = index of next smaller element, or n if none
    const rightBound = new Array(n).fill(n);
    
    // Find previous smaller element for each position
    const stack1: number[] = [];
    for (let i = 0; i < n; i++) {
        while (stack1.length > 0 && heights[stack1[stack1.length - 1]] >= heights[i]) {
            stack1.pop();
        }
        if (stack1.length > 0) {
            leftBound[i] = stack1[stack1.length - 1];
        }
        stack1.push(i);
    }
    
    // Find next smaller element for each position
    const stack2: number[] = [];
    for (let i = n - 1; i >= 0; i--) {
        while (stack2.length > 0 && heights[stack2[stack2.length - 1]] >= heights[i]) {
            stack2.pop();
        }
        if (stack2.length > 0) {
            rightBound[i] = stack2[stack2.length - 1];
        }
        stack2.push(i);
    }
    
    // Calculate maximum area
    let maxArea = 0;
    for (let i = 0; i < n; i++) {
        // Width extends from leftBound[i]+1 to rightBound[i]-1
        const width = rightBound[i] - leftBound[i] - 1;
        const area = heights[i] * width;
        maxArea = Math.max(maxArea, area);
    }
    
    return maxArea;
}
 
// For [2, 1, 5, 6, 2, 3]:
// leftBound  = [-1, -1, 1, 2, 1, 4]  (index of previous smaller)
// rightBound = [1, 6, 4, 4, 6, 6]   (index of next smaller, or n=6)
// 
// i=0: width = 1 - (-1) - 1 = 1, area = 2×1 = 2
// i=1: width = 6 - (-1) - 1 = 6, area = 1×6 = 6
// i=2: width = 4 - 1 - 1 = 2, area = 5×2 = 10
// i=3: width = 4 - 2 - 1 = 1, area = 6×1 = 6
// i=4: width = 6 - 1 - 1 = 4, area = 2×4 = 8
// i=5: width = 6 - 4 - 1 = 1, area = 3×1 = 3
// Maximum = 10

Trade-offs:

Approach	Passes	Clarity	Space
Single-pass	1	Lower (harder to debug)	O(n)
Pre-compute	3	Higher (easier to debug)	O(n)

Both are optimal in time and space complexity. In interviews, use whichever you're more comfortable implementing correctly under pressure!

Extension: Maximal Rectangle in Binary Matrix

Problem Statement (LeetCode 85):

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

matrix = [
  ['1','0','1','0','0'],
  ['1','0','1','1','1'],
  ['1','1','1','1','1'],
  ['1','0','0','1','0']
]

Output: 6 (the rectangle shown with *):
  ['1','0','1','0','0']
  ['1','0','*','*','*']
  ['1','1','*','*','*']
  ['1','0','0','1','0']

The Key Insight:

For each row, we can compute the 'height' at each column—how many consecutive 1's are stacked vertically ending at this row. This transforms each row into a histogram problem!

Algorithm:

Initialize a heights array of size columns, all zeros
For each row:
- Update heights: if matrix[row][col] is '1', increment heights[col]; else reset to 0
- Apply largest rectangle in histogram to this heights array
- Track maximum area across all rows

maximal-rectangle.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Maximal Rectangle in Binary Matrix
 * LeetCode 85
 * 
 * Reduce to histogram problem for each row
 */
function maximalRectangle(matrix: string[][]): number {
    if (matrix.length === 0 || matrix[0].length === 0) return 0;
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;
    
    for (let row = 0; row < rows; row++) {
        // Update heights for current row
        for (let col = 0; col < cols; col++) {
            if (matrix[row][col] === '1') {
                heights[col]++;
            } else {
                heights[col] = 0;  // Reset: '0' breaks the vertical stack
            }
        }
        
        // Apply histogram algorithm to current heights
        const area = largestRectangleInHistogram(heights);
        maxArea = Math.max(maxArea, area);
    }
    
    return maxArea;
}
 
// Trace for the example:
// Row 0: heights = [1, 0, 1, 0, 0], max histogram = 1
// Row 1: heights = [2, 0, 2, 1, 1], max histogram = 3
// Row 2: heights = [3, 1, 3, 2, 2], max histogram = 6 ← maximum!
// Row 3: heights = [4, 0, 0, 3, 0], max histogram = 4
// 
// Overall maximum = 6

The Reduction Pattern

This problem demonstrates a powerful technique: reducing a 2D problem to repeated applications of a 1D algorithm. By viewing each row as the 'ground level' of a histogram, we efficiently search all possible rectangles in O(rows × cols) time.

Complexity:

Time: O(rows × cols) — Each row processes in O(cols) using the histogram algorithm
Space: O(cols) — For the heights array and the stack

Related: Trapping Rain Water

Problem Statement (LeetCode 42):

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

Example:

heights = [0,1,0,2,1,0,1,3,2,1,2,1]

               ┌───┐
       ┌───┐≈≈≈│   │
   ┌───┤   ├───┤   ├───┐   ┌───┐
   │   │   │   │   │   │   │   │
   │   │   │   │   │   ├───┤   ├───┐
───┴───┴───┴───┴───┴───┴───┴───┴───┴───
 0   1   0   2   1   0   1   3   2   1   2   1

Water trapped = 6 (shown as ≈)

Monotonic Stack Approach:

We use a monotonically decreasing stack. The key insight: water can only be trapped in 'valleys'—when we find a bar that's taller than a previous bar, we can fill the space between with water.

Algorithm:

Maintain a decreasing stack of indices
When we find a bar taller than the stack top, water is trapped
Pop the bottom of the valley; the new top is the left boundary
Calculate water trapped in this 'layer' between left boundary and current position

trapping-water.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Trapping Rain Water with Monotonic Stack
 * LeetCode 42
 */
function trap(height: number[]): number {
    const n = height.length;
    const stack: number[] = [];  // Monotonically decreasing stack of indices
    let water = 0;
    
    for (let i = 0; i < n; i++) {
        // While current bar is taller than stack top, water is trapped
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const bottom = stack.pop()!;  // This is the valley bottom
            
            if (stack.length === 0) break;  // No left wall, water leaks
            
            const left = stack[stack.length - 1];  // Left wall
            const right = i;  // Right wall
            
            // Water level is limited by the shorter wall
            const h = Math.min(height[left], height[right]) - height[bottom];
            const w = right - left - 1;
            
            water += h * w;
        }
        
        stack.push(i);
    }
    
    return water;
}
 
// The stack approach fills water "layer by layer" horizontally
// Each iteration calculates one horizontal slice of trapped water

Stack vs Two-Pointer for Trapping Water

While the monotonic stack approach works, many prefer the two-pointer approach for trapping water as it's more intuitive (O(n) time, O(1) space). Both are valid; understand both approaches to choose based on context.

Summary: Histogram Problems Mastered

You've now conquered the most challenging monotonic stack problems. Let's consolidate your mastery:

Key Takeaways

•Histogram area is about finding boundaries: The left boundary is the previous smaller element; the right boundary is the next smaller element.
•The monotonically increasing stack finds both boundaries: Elements on the stack when popped reveal their right boundary; the new stack top is the left boundary.
•The sentinel trick simplifies code: Appending a 0-height bar ensures all elements are processed.
•Width = right - left - 1: The rectangle extends from (left + 1) to (right - 1) inclusive.
•2D problems reduce to 1D: Build histograms row by row and apply the 1D algorithm.
•Trapping water uses decreasing stacks: We're looking for 'valleys' bounded by taller bars on both sides.

Module 9: Complete Problem Reference
Problem	Stack Type	Key Insight	Complexity
Next Greater Element	Decreasing	Pop smaller elements	O(n)
Next Smaller Element	Increasing	Pop larger elements	O(n)
Daily Temperatures	Decreasing	NGE with distance	O(n)
Stock Span	Decreasing	Previous greater	O(n)
Largest Rectangle in Histogram	Increasing	Find left/right smaller	O(n)
Maximal Rectangle in Matrix	Increasing	Row-by-row histogram	O(m×n)
Trapping Rain Water	Decreasing	Find valleys	O(n)

Congratulations!

You've completed the Monotonic Stacks module. This advanced pattern transforms seemingly complex problems into elegant O(n) solutions. The intuition you've built here—maintaining structure to efficiently answer ordering questions—will serve you well across algorithm design.

Remember: monotonic stacks are about recognizing when relative ordering matters and maintaining just enough state to answer queries efficiently. When you see 'next/previous greater/smaller' or 'boundaries defined by relative heights,' think monotonic stack!

Module Complete

You have mastered monotonic stacks—from the basic concept through both variants to the crown jewel histogram problems. You can now tackle any monotonic stack problem with confidence, recognizing patterns and selecting the right approach. This knowledge places you among the top percentile of algorithm practitioners.

4 / 4

Loading learning content...

Data Structures & AlgorithmsMonotonic Stacks

Monotonic Stacks — Advanced Pattern

LevelIntermediate

Duration50 mins

TopicMonotonic Stacks

4 / 4

Histogram Area and Related Problems

The Crown Jewel of Monotonic Stack Problems

This problem is special because it combines multiple concepts:

Finding both left and right boundaries
Understanding how smaller elements limit the extent of rectangles
Efficiently computing areas in a single pass

Mastering this problem unlocks solutions to an entire family of related problems, including the famous 'Maximal Rectangle in Binary Matrix.'

What You Will Learn

The Problem: Largest Rectangle in Histogram

Problem Statement (LeetCode 84):

Visual Example:

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

     ┌───┐
     │   │
   ┌─┤   │
   │ │   ├───┐
   │ │   │   │   ┌───┐
 ┌─┤ │   │   ├───┤   │
 │ │ │   │   │   │   │
─┴─┴─┴───┴───┴───┴───┴─
  2 1   5   6   2   3

Answer: 10

The largest rectangle has height 5 and width 2 (covering indices 2 and 3 with heights 5 and 6, where the limiting height is 5).

     ┌───┬───┐
     │███│███│
   ┌─┤███│███│
   │ │███│███├───┐
   │ │███│███│   │   ┌───┐
 ┌─┤ │███│███│   ├───┤   │
 │ │ │███│███│   │   │   │
─┴─┴─┴───┴───┴───┴───┴───┴─
  2 1   5   6   2   3

The Core Insight

Brute Force: Understanding the Structure

Before diving into the optimal solution, let's understand the structure through brute force:

Approach 1: Try All Pairs (O(n²) or O(n³))

For each pair of indices (i, j), the maximum rectangle is:

Width = j - i + 1
Height = minimum height between i and j
Area = width × height

This requires O(n²) pairs and O(n) to find minimum in each pair → O(n³).

With prefix minimum optimization → O(n²).

Approach 2: Expand from Each Bar (O(n²))

For each bar i, treat it as the limiting height and expand:

Find the leftmost bar ≥ heights[i]
Find the rightmost bar ≥ heights[i]
Width = right - left + 1
Area = heights[i] × width

histogram-brute.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Brute Force: O(n²)
 * For each bar, expand left and right while height >= current
 */
function largestRectangleBrute(heights: number[]): number {
    const n = heights.length;
    let maxArea = 0;
    
    for (let i = 0; i < n; i++) {
        const h = heights[i];
        
        // Find left boundary: first bar to left that is shorter
        let left = i;
        while (left > 0 && heights[left - 1] >= h) {
            left--;
        }
        
        // Find right boundary: first bar to right that is shorter
        let right = i;
        while (right < n - 1 && heights[right + 1] >= h) {
            right++;
        }
        
        // Calculate area with current bar as the limiting height
        const width = right - left + 1;
        const area = h * width;
        maxArea = Math.max(maxArea, area);
    }
    
    return maxArea;
}
 
// For [2, 1, 5, 6, 2, 3]:
// Bar 0 (h=2): left=0, right=0 (bar 1 has h=1 < 2), area = 2×1 = 2
// Bar 1 (h=1): left=0, right=5 (all bars ≥ 1), area = 1×6 = 6
// Bar 2 (h=5): left=2, right=3 (bar 4 has h=2 < 5), area = 5×2 = 10
// Bar 3 (h=6): left=3, right=3 (bar 2 has h=5 < 6), area = 6×1 = 6
// Bar 4 (h=2): left=2, right=5 (bar 1 has h=1 < 2), area = 2×4 = 8
// Bar 5 (h=3): left=5, right=5 (bar 4 has h=2 < 3), area = 3×1 = 3
// Maximum = 10

Key Observation:

The left boundary is the first shorter bar to the left (i.e., Previous Smaller Element). The right boundary is the first shorter bar to the right (i.e., Next Smaller Element).

This is exactly what a monotonically increasing stack computes efficiently!

The Optimal Monotonic Stack Solution

We use a monotonically increasing stack to find both the Next Smaller Element (right boundary) and Previous Smaller Element (left boundary) in a single pass.

Algorithm:

Maintain an increasing stack of indices
When we encounter a bar shorter than the stack top, the current bar is the right boundary for the top
The element below the top in the stack is the left boundary for the top
Pop the top and calculate its area
Continue until the stack is empty or the current bar is no longer shorter
Push the current index

histogram-optimal.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Optimal Solution: O(n) time, O(n) space
 * Monotonically increasing stack
 */
function largestRectangleInHistogram(heights: number[]): number {
    const n = heights.length;
    const stack: number[] = [];  // Stack of indices
    let maxArea = 0;
    
    // Process all bars, then handle remaining stack
    for (let i = 0; i <= n; i++) {
        // Treat index n as having height 0 (sentinel to flush the stack)
        const currentHeight = i < n ? heights[i] : 0;
        
        // While stack is not empty and current height is less than stack top
        while (stack.length > 0 && currentHeight < heights[stack[stack.length - 1]]) {
            // Pop the index whose right boundary we've found
            const poppedIndex = stack.pop()!;
            const h = heights[poppedIndex];
            
            // Left boundary: position after the new stack top (or 0 if stack empty)
            // Right boundary: i - 1 (current position - 1)
            // Width = right - left + 1 = (i - 1) - left + 1 = i - left
            //       = i - (stack.top() + 1) = i - stack.top() - 1  [if stack not empty]
            //       = i - 0 = i  [if stack empty, left boundary is 0]
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            
            const area = h * width;
            maxArea = Math.max(maxArea, area);
        }
        
        stack.push(i);
    }
    
    return maxArea;
}

Detailed Trace for [2, 1, 5, 6, 2, 3]:

Step-by-Step Trace
i	height[i]	Stack Before	Actions	Stack After	maxArea
0	2	[]	Push 0	[0]	0
1	1	[0]	1 < 2: Pop 0, h=2, w=1, area=2; Push 1	[1]	2
2	5	[1]	5 > 1: Push 2	[1, 2]	2
3	6	[1, 2]	6 > 5: Push 3	[1, 2, 3]	2
4	2	[1, 2, 3]	2 < 6: Pop 3, h=6, w=4-2-1=1, area=6; 2 < 5: Pop 2, h=5, w=4-1-1=2, area=10; Push 4	[1, 4]	10
5	3	[1, 4]	3 > 2: Push 5	[1, 4, 5]	10
6	0 (sentinel)	[1, 4, 5]	0 < 3: Pop 5, h=3, w=6-4-1=1, area=3; 0 < 2: Pop 4, h=2, w=6-1-1=4, area=8; 0 < 1: Pop 1, h=1, w=6, area=6	[]	10

The Sentinel Trick

Understanding the Width Calculation

The width calculation is often the trickiest part. Let's break it down precisely.

When we pop index p because of current index i:

Right boundary: i - 1 (the bar at i is shorter, so we can only extend to i - 1)
Left boundary: stack.top() + 1 after popping (the bar below p in the stack is the previous smaller element, so we can only extend from stack.top() + 1)

If stack is empty after popping, there's no shorter bar to the left, so left boundary is 0.

Width formula:

if stack is empty:
    width = i  // From 0 to i-1, that's i bars
else:
    width = i - stack.top() - 1  // From stack.top()+1 to i-1

width-visualization.pseudo

Visualization

// Example: heights = [1, 5, 4, 3, 2]
// When processing i=4 (height 2):
// Stack = [0, 1, 2, 3] (heights: 1, 5, 4, 3)
 
// Pop index 3 (height 3):
//   Right boundary = i - 1 = 3
//   Stack now = [0, 1, 2], top = 2
//   Left boundary = stack.top() + 1 = 2 + 1 = 3
//   Hmm, left = right = 3, width = 1
//   Area = 3 × 1 = 3
 
// Pop index 2 (height 4):
//   Right boundary = i - 1 = 3
//   Stack now = [0, 1], top = 1
//   Left boundary = stack.top() + 1 = 1 + 1 = 2
//   Width = 3 - 2 + 1 = 2  or  i - stack.top() - 1 = 4 - 1 - 1 = 2
//   Area = 4 × 2 = 8
 
// Pop index 1 (height 5):
//   Right boundary = i - 1 = 3
//   Stack now = [0], top = 0
//   Left boundary = stack.top() + 1 = 0 + 1 = 1
//   Width = 3 - 1 + 1 = 3  or  i - stack.top() - 1 = 4 - 0 - 1 = 3
//   Area = 5 × 3 = 15
 
// Height 2 at index 4 doesn't pop height 1 at index 0
// Push index 4
 
// Later, sentinel at index 5 pops remaining:
// Pop index 4 (height 2):
//   Stack = [0], width = 5 - 0 - 1 = 4
//   Area = 2 × 4 = 8
 
// Pop index 0 (height 1):
//   Stack = [], width = 5 (all bars)
//   Area = 1 × 5 = 5
 
// Maximum area = 15

Why This Formula Works

Alternative: Pre-compute Boundaries

Some find the single-pass solution hard to reason about. An alternative is to explicitly pre-compute the left and right boundaries using two separate passes, then compute areas in a third pass.

This is slightly less elegant but easier to understand and debug.

histogram-precompute.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Alternative: Pre-compute boundaries explicitly
 * Still O(n) time, O(n) space, but clearer logic
 */
function largestRectanglePrecompute(heights: number[]): number {
    const n = heights.length;
    
    // leftBound[i] = index of previous smaller element, or -1 if none
    const leftBound = new Array(n).fill(-1);
    // rightBound[i] = index of next smaller element, or n if none
    const rightBound = new Array(n).fill(n);
    
    // Find previous smaller element for each position
    const stack1: number[] = [];
    for (let i = 0; i < n; i++) {
        while (stack1.length > 0 && heights[stack1[stack1.length - 1]] >= heights[i]) {
            stack1.pop();
        }
        if (stack1.length > 0) {
            leftBound[i] = stack1[stack1.length - 1];
        }
        stack1.push(i);
    }
    
    // Find next smaller element for each position
    const stack2: number[] = [];
    for (let i = n - 1; i >= 0; i--) {
        while (stack2.length > 0 && heights[stack2[stack2.length - 1]] >= heights[i]) {
            stack2.pop();
        }
        if (stack2.length > 0) {
            rightBound[i] = stack2[stack2.length - 1];
        }
        stack2.push(i);
    }
    
    // Calculate maximum area
    let maxArea = 0;
    for (let i = 0; i < n; i++) {
        // Width extends from leftBound[i]+1 to rightBound[i]-1
        const width = rightBound[i] - leftBound[i] - 1;
        const area = heights[i] * width;
        maxArea = Math.max(maxArea, area);
    }
    
    return maxArea;
}
 
// For [2, 1, 5, 6, 2, 3]:
// leftBound  = [-1, -1, 1, 2, 1, 4]  (index of previous smaller)
// rightBound = [1, 6, 4, 4, 6, 6]   (index of next smaller, or n=6)
// 
// i=0: width = 1 - (-1) - 1 = 1, area = 2×1 = 2
// i=1: width = 6 - (-1) - 1 = 6, area = 1×6 = 6
// i=2: width = 4 - 1 - 1 = 2, area = 5×2 = 10
// i=3: width = 4 - 2 - 1 = 1, area = 6×1 = 6
// i=4: width = 6 - 1 - 1 = 4, area = 2×4 = 8
// i=5: width = 6 - 4 - 1 = 1, area = 3×1 = 3
// Maximum = 10

Trade-offs:

Approach	Passes	Clarity	Space
Single-pass	1	Lower (harder to debug)	O(n)
Pre-compute	3	Higher (easier to debug)	O(n)

Both are optimal in time and space complexity. In interviews, use whichever you're more comfortable implementing correctly under pressure!

Extension: Maximal Rectangle in Binary Matrix

Problem Statement (LeetCode 85):

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

matrix = [
  ['1','0','1','0','0'],
  ['1','0','1','1','1'],
  ['1','1','1','1','1'],
  ['1','0','0','1','0']
]

Output: 6 (the rectangle shown with *):
  ['1','0','1','0','0']
  ['1','0','*','*','*']
  ['1','1','*','*','*']
  ['1','0','0','1','0']

The Key Insight:

For each row, we can compute the 'height' at each column—how many consecutive 1's are stacked vertically ending at this row. This transforms each row into a histogram problem!

Algorithm:

Initialize a heights array of size columns, all zeros
For each row:
- Update heights: if matrix[row][col] is '1', increment heights[col]; else reset to 0
- Apply largest rectangle in histogram to this heights array
- Track maximum area across all rows

maximal-rectangle.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Maximal Rectangle in Binary Matrix
 * LeetCode 85
 * 
 * Reduce to histogram problem for each row
 */
function maximalRectangle(matrix: string[][]): number {
    if (matrix.length === 0 || matrix[0].length === 0) return 0;
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;
    
    for (let row = 0; row < rows; row++) {
        // Update heights for current row
        for (let col = 0; col < cols; col++) {
            if (matrix[row][col] === '1') {
                heights[col]++;
            } else {
                heights[col] = 0;  // Reset: '0' breaks the vertical stack
            }
        }
        
        // Apply histogram algorithm to current heights
        const area = largestRectangleInHistogram(heights);
        maxArea = Math.max(maxArea, area);
    }
    
    return maxArea;
}
 
// Trace for the example:
// Row 0: heights = [1, 0, 1, 0, 0], max histogram = 1
// Row 1: heights = [2, 0, 2, 1, 1], max histogram = 3
// Row 2: heights = [3, 1, 3, 2, 2], max histogram = 6 ← maximum!
// Row 3: heights = [4, 0, 0, 3, 0], max histogram = 4
// 
// Overall maximum = 6

The Reduction Pattern

Complexity:

Time: O(rows × cols) — Each row processes in O(cols) using the histogram algorithm
Space: O(cols) — For the heights array and the stack

Related: Trapping Rain Water

Problem Statement (LeetCode 42):

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.

Example:

heights = [0,1,0,2,1,0,1,3,2,1,2,1]

               ┌───┐
       ┌───┐≈≈≈│   │
   ┌───┤   ├───┤   ├───┐   ┌───┐
   │   │   │   │   │   │   │   │
   │   │   │   │   │   ├───┤   ├───┐
───┴───┴───┴───┴───┴───┴───┴───┴───┴───
 0   1   0   2   1   0   1   3   2   1   2   1

Water trapped = 6 (shown as ≈)

Monotonic Stack Approach:

We use a monotonically decreasing stack. The key insight: water can only be trapped in 'valleys'—when we find a bar that's taller than a previous bar, we can fill the space between with water.

Algorithm:

Maintain a decreasing stack of indices
When we find a bar taller than the stack top, water is trapped
Pop the bottom of the valley; the new top is the left boundary
Calculate water trapped in this 'layer' between left boundary and current position

trapping-water.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Trapping Rain Water with Monotonic Stack
 * LeetCode 42
 */
function trap(height: number[]): number {
    const n = height.length;
    const stack: number[] = [];  // Monotonically decreasing stack of indices
    let water = 0;
    
    for (let i = 0; i < n; i++) {
        // While current bar is taller than stack top, water is trapped
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const bottom = stack.pop()!;  // This is the valley bottom
            
            if (stack.length === 0) break;  // No left wall, water leaks
            
            const left = stack[stack.length - 1];  // Left wall
            const right = i;  // Right wall
            
            // Water level is limited by the shorter wall
            const h = Math.min(height[left], height[right]) - height[bottom];
            const w = right - left - 1;
            
            water += h * w;
        }
        
        stack.push(i);
    }
    
    return water;
}
 
// The stack approach fills water "layer by layer" horizontally
// Each iteration calculates one horizontal slice of trapped water

Stack vs Two-Pointer for Trapping Water

Summary: Histogram Problems Mastered

You've now conquered the most challenging monotonic stack problems. Let's consolidate your mastery:

Key Takeaways

•Histogram area is about finding boundaries: The left boundary is the previous smaller element; the right boundary is the next smaller element.
•The monotonically increasing stack finds both boundaries: Elements on the stack when popped reveal their right boundary; the new stack top is the left boundary.
•The sentinel trick simplifies code: Appending a 0-height bar ensures all elements are processed.
•Width = right - left - 1: The rectangle extends from (left + 1) to (right - 1) inclusive.
•2D problems reduce to 1D: Build histograms row by row and apply the 1D algorithm.
•Trapping water uses decreasing stacks: We're looking for 'valleys' bounded by taller bars on both sides.

Module 9: Complete Problem Reference
Problem	Stack Type	Key Insight	Complexity
Next Greater Element	Decreasing	Pop smaller elements	O(n)
Next Smaller Element	Increasing	Pop larger elements	O(n)
Daily Temperatures	Decreasing	NGE with distance	O(n)
Stock Span	Decreasing	Previous greater	O(n)
Largest Rectangle in Histogram	Increasing	Find left/right smaller	O(n)
Maximal Rectangle in Matrix	Increasing	Row-by-row histogram	O(m×n)
Trapping Rain Water	Decreasing	Find valleys	O(n)

Congratulations!

Module Complete

4 / 4