Trapping Rain Water

Difficulty: Hard
Topics: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack
Link: https://leetcode.com/problems/trapping-rain-water/

Problem Description

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

Example 1:


Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:


Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Solution

1. Problem Deconstruction

Rewrite the Problem

Technical Version:
Given an array height of non-negative integers representing bar heights in an elevation map, compute the total water volume trapped between bars after rainfall. Water trapping occurs when lower bars are bounded by higher bars on both left and right sides. Formally, for each index i, the trapped water is determined by the minimum of the maximum heights to its left and right, minus its own height, provided this value is non-negative.

Beginner Version:
Imagine a series of adjacent bars with different heights. When rain falls, water collects in the gaps between bars. The amount of water trapped at any gap depends on the height of the tallest bars to its left and right. We need to calculate the total water accumulated across all gaps.

Mathematical Version:
Let H = [h₀, h₁, ..., hₙ₋₁] be the height array. Define:

L[i] = max(h₀, h₁, ..., hᵢ) (left maximum)
R[i] = max(hᵢ, hᵢ₊₁, ..., hₙ₋₁) (right maximum)

The water trapped at index i is:
W[i] = max(0, min(L[i], R[i]) - hᵢ)

The total trapped water is:
T = ∑ W[i] for i ∈ [0, n-1]

Constraint Analysis

n == height.length: The array size directly determines computation scope. Must handle empty arrays.
1 <= n <= 2 * 10⁴: Rules out O(n²) solutions (e.g., brute-force nested loops), as 20k² = 400M operations, exceeding Python’s practical limits. Requires O(n log n) or better.
0 <= height[i] <= 10⁵: Zero-height bars can still trap water. Large values risk integer overflow in cumulative sums, but Python handles big integers.

Hidden Edge Cases:

All zeros: No water trapped.
Monotonic sequences (strictly increasing/decreasing): Zero trapped water except at endpoints.
Single peak: Water trapped symmetrically around peak.
Multiple peaks: Complex water distribution between peaks.

2. Intuition Scaffolding

Analogies

Real-World Metaphor: Like valleys between mountains—water fills until it reaches the lowest pass leading outward. Each valley’s capacity is constrained by the shorter surrounding mountain.
Gaming Analogy: In tower defense games, water pools between towers of varying heights. The water level cannot exceed the height of the shortest flanking tower.
Math Analogy: Finding the “concave hull” of the elevation graph. Water fills the gaps between the original curve and the upper envelope formed by left/right maxima.

Common Pitfalls

Assuming immediate neighbors determine water: Water trapping depends on global left/right maxima, not adjacent bars.
Overlooking zero-height bars: They contribute to water volume if bounded by higher bars.
Misusing two-pointer boundaries: Incorrect pointer movement leads to missed water pockets.
Stack misinterpretation: Using stacks without accounting for horizontal distance between bars.
Ignoring descending sequences: Right-side maxima must be computed in reverse order.

3. Approach Encyclopedia

Approach 1: Brute Force

Pseudocode:

def trap_brute(height):
    n = len(height)
    total = 0
    for i in range(n):
        left_max = max(height[:i+1])  # Scan left
        right_max = max(height[i:])   # Scan right
        total += min(left_max, right_max) - height[i]
    return total

Complexity Proof:

Time: O(n²) — Each of n indices requires O(n) scans.
Space: O(1) — No extra storage.
Visualization:

Index 2: left_max = max([0,1,0]) = 1, right_max = max([0,2,1,...]) = 3 → water = 1 - 0 = 1

Approach 2: Dynamic Programming (Precomputation)

Pseudocode:

def trap_dp(height):
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]
    right_max[-1] = height[-1]
    
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    
    return sum(min(l, r) - h for l, r, h in zip(left_max, right_max, height))

Complexity Proof:

Time: O(n) — Three linear passes.
Space: O(n) — Two auxiliary arrays.
Visualization:

left_max  = [0,1,1,2,2,2,2,3,3,3,3,3]
right_max = [3,3,3,3,3,3,3,3,2,2,2,1]
Water: [0,0,1,0,1,2,1,0,0,1,0,0] → Sum=6

Approach 3: Stack-Based

Pseudocode:

def trap_stack(height):
    stack = []
    total = 0
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            top = stack.pop()
            if not stack: break
            width = i - stack[-1] - 1
            bounded_height = min(h, height[stack[-1]]) - height[top]
            total += width * bounded_height
        stack.append(i)
    return total

Complexity Proof:

Time: O(n) — Each index pushed/popped once.
Space: O(n) — Stack worst-case size.
Visualization:

Stack state at i=7: [3,6,7] → Pop 7, then 6: compute water between height[3] and height[7].

Approach 4: Two Pointers (Optimal)

Pseudocode:

def trap(height):
    left, right = 0, len(height)-1
    left_max = right_max = 0
    total = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            total += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            total += right_max - height[right]
            right -= 1
    return total

Complexity Proof:

Time: O(n) — Single pass.
Space: O(1) — Constant variables.
Visualization:

Step: left=0, right=11 → left_max=0, right_max=1 → move left → add 0.
Step: left=1, right=11 → left_max=1, add 0 → left=2, add 1 → etc.

4. Code Deep Dive

Two-Pointer Code with Annotations:

def trap(height):
    if not height:  # Handle empty array
        return 0
    left, right = 0, len(height)-1  # Initialize pointers
    left_max = right_max = 0  # Track current maxima
    total = 0
    while left < right:
        # Prefer moving pointer with smaller current height
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]  # Update left max
            else:
                total += left_max - height[left]  # Add water
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]  # Update right max
            else:
                total += right_max - height[right]  # Add water
            right -= 1
    return total

Edge Case Handling:

Empty Array: Early return 0 (Line 2-3).
Example 2 ([4,2,0,3,2,5]):
- Left moves first: at index1, left_max=4 → add 2 (4-2).
- Left moves to index2: add 4 (4-0).
- Left moves to index3: add 1 (4-3).
- Right moves from index5 to index4: right_max=5 → add 2 (5-2).
- Total: 2+4+1+2=9.

5. Complexity War Room

Hardware-Aware Analysis:

Two-pointer approach uses 5 integers (≈20 bytes), fitting in CPU registers.
For n=20k, the loop runs in ≈20k cycles, leveraging L1/L2 cache locality.

Approach Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	High	❌ (Fails large n)
DP Precomputation	O(n)	O(n)	Medium	✅ (Clear logic)
Stack	O(n)	O(n)	Low	✅ (Advanced)
Two Pointers	O(n)	O(1)	Medium	✅ (Optimal)

6. Pro Mode Extras

Variants:

Trapping Rain Water II (3D): Use priority queues to handle elevation maps in 2D.
Container With Most Water: Focuses on max area between two bars (no summation).
k Transactions Allowed: Dynamic programming with state tracking (e.g., LeetCode 123).

Interview Cheat Sheet:

First Mention: Always state time/space complexity upfront.
Brute Force: Acknowledge it, then dismiss due to constraints.
Key Insight: Water trapped at i is bounded by min(left_max, right_max).
Two-Pointer Rationale: Moving the shorter pointer ensures correctness.

#42 - Trapping Rain Water

Trapping Rain Water

Problem Description

Solution

1. Problem Deconstruction

Rewrite the Problem

Constraint Analysis

2. Intuition Scaffolding

Analogies

Common Pitfalls

3. Approach Encyclopedia

Approach 1: Brute Force

Approach 2: Dynamic Programming (Precomputation)

Approach 3: Stack-Based

Approach 4: Two Pointers (Optimal)

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras