Trapping Rain Water Using Stack — Step-by-Step Stack Approach Explained

Trapping Rain Water (LeetCode 42) is a classic hard problem. Most tutorials teach the two-pointer or prefix-max solution. Here we focus on the stack-based approach, which processes water layer by layer instead of column by column.

The Problem

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

Input:  [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Three Approaches Overview

Approach	Time	Space	Style
Prefix max arrays	O(n)	O(n)	Column by column
Two pointers	O(n)	O(1)	Column by column
Stack	O(n)	O(n)	Layer by layer

All three are O(n) time. The stack approach is unique because it calculates water in horizontal layers bounded by walls, not vertical columns.

The Stack Intuition

Imagine scanning left to right. Whenever you find a bar taller than the previous one, there might be a basin between the current bar and some earlier tall bar. The stack keeps track of bars that could form the left wall of a basin.

1. Push bar indices onto a monotonic decreasing stack
2. When the current bar is taller than the stack top, that top is the bottom of a basin
3. The new stack top (after pop) is the left wall
4. The current bar is the right wall
5. Calculate the water trapped in that horizontal strip

Python Implementation

def trap(height):
    """
    Stack-based trapping rain water.
    Time: O(n) — each index pushed/popped at most once.
    Space: O(n) — for the stack.
    """
    stack = []  # monotonic decreasing stack of indices
    water = 0

    for i in range(len(height)):
        # While current bar is taller than stack top
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()

            if not stack:
                break  # no left wall

            left = stack[-1]
            # Width between left wall and current bar
            width = i - left - 1
            # Height is bounded by shorter wall minus the bottom
            h = min(height[i], height[left]) - height[bottom]
            water += width * h

        stack.append(i)

    return water

Detailed Trace

Let us trace through height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

i=0, h=0: stack=[]       → push 0              stack=[0]
i=1, h=1: h[0]=0 < 1    → pop 0 (bottom=0)
           stack empty    → break
           push 1                               stack=[1]
i=2, h=0: h[1]=1 > 0    → no pop, push 2       stack=[1,2]
i=3, h=2: h[2]=0 < 2    → pop 2 (bottom=0)
           left=1, w=3-1-1=1, h=min(2,1)-0=1   → water += 1  (total=1)
           h[1]=1 < 2    → pop 1 (bottom=1)
           stack empty    → break
           push 3                               stack=[3]
i=4, h=1: h[3]=2 > 1    → no pop, push 4       stack=[3,4]
i=5, h=0: h[4]=1 > 0    → no pop, push 5       stack=[3,4,5]
i=6, h=1: h[5]=0 < 1    → pop 5 (bottom=0)
           left=4, w=6-4-1=1, h=min(1,1)-0=1   → water += 1  (total=2)
           h[4]=1 = 1    → no pop, push 6       stack=[3,4,6]
i=7, h=3: h[6]=1 < 3    → pop 6 (bottom=1)
           left=4, w=7-4-1=2, h=min(3,1)-1=0   → water += 0
           h[4]=1 < 3    → pop 4 (bottom=1)
           left=3, w=7-3-1=3, h=min(3,2)-1=1   → water += 3  (total=5)
           h[3]=2 < 3    → pop 3 (bottom=2)
           stack empty    → break
           push 7                               stack=[7]
i=8, h=2: h[7]=3 > 2    → no pop, push 8       stack=[7,8]
i=9, h=1: no pop, push 9                        stack=[7,8,9]
i=10,h=2: h[9]=1 < 2    → pop 9 (bottom=1)
           left=8, w=10-8-1=1, h=min(2,2)-1=1  → water += 1  (total=6)
           h[8]=2 = 2    → no pop, push 10      stack=[7,8,10]
i=11,h=1: no pop, push 11                       stack=[7,8,10,11]

Final answer: 6 ✓

Comparison with Two-Pointer

def trap_two_pointer(height):
    """Two-pointer approach for comparison. O(n) time, O(1) space."""
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

When to prefer the stack approach:

• You need to identify each bounded region (not just the total volume)
• The problem is a 2D variant where you process layers
• You are already using a stack for related work (e.g., largest rectangle)

When to prefer two-pointer:

• You only need the total volume
• You want O(1) space

Edge Cases

1. Empty or single bar — [] or [5] → 0
2. Flat surface — [3, 3, 3] → 0 (no basin)
3. Ascending — [1, 2, 3] → 0 (water runs off right)
4. Descending — [3, 2, 1] → 0 (water runs off left)
5. V shape — [3, 0, 3] → 3
6. All zeros — [0, 0, 0] → 0

Complexity Analysis

Metric	Value
Time	O(n) — each index pushed and popped at most once
Space	O(n) — stack can hold up to n indices

When to Use This Pattern

The stack-based rain water approach is useful when:

• You are solving a bounded region problem on a 1D elevation map
• You want to decompose trapped water into horizontal strips
• You need to extend the solution to report where water is trapped
• Interview asks for “solve with a stack” specifically

Related Problems

Problem	Difficulty	Key Idea
LeetCode 42 — Trapping Rain Water	Hard	This problem
LeetCode 84 — Largest Rectangle in Histogram	Hard	Similar stack pattern
LeetCode 407 — Trapping Rain Water II	Hard	3D version with priority queue
LeetCode 11 — Container With Most Water	Medium	Two-pointer on walls

Key Takeaway

The stack approach to Trapping Rain Water processes water horizontally — it finds basins formed between walls and computes water layer by layer. While the two-pointer approach is more space-efficient, the stack approach gives you deeper insight into bounded-region problems and is the foundation for harder variants.