LeetCode · #42

Trapping Rain Water Solution

Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #42

🏗️

Pattern

Two Pointers — left-max / right-max

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. Water at each position is determined by the minimum of the tallest bars on its left and right, minus its own height.

Example

 Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6 // 6 units of water trapped between the bars 

Constraints

 • n == height.length • 1 ≤ n ≤ 2 × 10⁴ • 0 ≤ height[i] ≤ 10⁵ 

Section Two · Approach 1

Brute Force — O(n²)

For each bar, scan left to find the tallest bar to its left, scan right for the tallest bar to its right. Water at position i = min(leftMax, rightMax) - height[i]. Two linear scans per bar = O(n²).

Why we can do better

Problem: Re-scanning for leftMax and rightMax at every position wastes work. Precomputing prefix-max and suffix-max arrays makes it O(n) with O(n) space. Two pointers eliminate even those arrays for O(1) space.

Java — Brute Force

 class Solution {
public int trap(int[] height) {
int water = 0;
for (int i = 1; i < height.length - 1; i++) {
int leftMax = 0, rightMax = 0;
for (int j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]);
for (int j = i; j < height.length; j++) rightMax = Math.max(rightMax, height[j]);
            water += Math.min(leftMax, rightMax) - height[i];
        }
return water;
    }
}

Python — Brute Force

 class Solution:
def trap(self, height: list[int]) -> int:
        water = 0 for i in range(1, len(height) - 1):
            left_max = max(height[:i + 1])
            right_max = max(height[i:])
            water += min(left_max, right_max) - height[i]
return water

Metric	Value
Time	O(n²) — linear scan per position
Space	O(1)

Section Three · Approach 2

Two Pointers — O(n) time, O(1) space

Maintain leftMax and rightMax as we move pointers inward from both ends. At each step, process the side with the smaller max — because that side's water level is determined (the other side is guaranteed to be at least as tall).

💡 Mental model: Imagine two walls of a valley closing in from opposite sides. Each wall remembers the tallest ridge it has seen so far. The shorter wall determines the water level for the bar it's currently looking at — because even if the other side has gaps, the shorter wall is the bottleneck. Process the shorter side, then step it inward.

Algorithm

Step 1: left = 0, right = n-1, leftMax = 0, rightMax = 0.
Step 2: While left < right:
Step 3: If height[left] < height[right]: update leftMax. Water at left = leftMax - height[left]. left++.
Step 4: Else: update rightMax. Water at right = rightMax - height[right]. right--.

🎯 Why the shorter side is safe to process:

If height[left] < height[right], we know the right side has at least height[right] as a wall.
So the water at left depends only on leftMax — the right side is guaranteed tall enough.
We don't need to know the exact rightMax. This is the key insight that eliminates the need for prefix arrays.

Intermediate approach — prefix arrays:

Precompute leftMax[i] = max(height[0..i]) and rightMax[i] = max(height[i..n-1]).
Then water at i = min(leftMax[i], rightMax[i]) - height[i].
This is O(n) time and O(n) space — good for understanding, but the two-pointer approach eliminates the arrays.

Section Four · Trace

Visual Walkthrough

Trace through height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

Two Pointers — process shorter side, track running max

Section Five · Implementation

Code — Java & Python

Java — Two Pointers

 class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                water += leftMax - height[left]; // trapped at left
left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                water += rightMax - height[right]; // trapped at right
right--;
            }
        }
return water;
    }
}

Python — Two Pointers

 class Solution:
def trap(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
left_max = right_max = water = 0 while left < right:
if height[left] < height[right]:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1 else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1 return water

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force (per bar)	O(n²)	O(1)	Re-scans for max at each bar
Prefix/Suffix Max Arrays	O(n)	O(n)	Two extra arrays; clearer logic
Monotonic Stack	O(n)	O(n)	Row-by-row water; more complex to implement
Two Pointers ← optimal	O(n)	O(1)	Process shorter side; running max replaces arrays

Prefix arrays as a stepping stone:

If the two-pointer approach feels unintuitive, first implement the prefix-max/suffix-max version.
Once you see that you only ever need leftMax[i] and rightMax[i] at each position, you realize two running variables suffice — and the two-pointer technique emerges naturally.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Flat	`[3, 3, 3]`	No valleys — water = 0 everywhere.
Ascending	`[1, 2, 3, 4]`	No valleys — water slides off to the left.
Descending	`[4, 3, 2, 1]`	No valleys — water slides off to the right.
Single valley	`[3, 0, 3]`	Water = min(3,3) - 0 = 3 at index 1.
All zeros	`[0, 0, 0]`	No walls to hold water → 0.
Single bar	`[5]`	No pair of walls → 0. Pointers cross immediately.

⚠ Common Mistake: Updating leftMax after computing water instead of before. The correct order is: update max first (leftMax = max(leftMax, height[left])), then compute water (leftMax - height[left]). If the current bar is taller than leftMax, it becomes the new max and traps 0 water — not a negative amount.

← Back to Two Pointers problems

LearningTree

LC 42 · Trapping Rain Water — Solution & Explanation | DSA Guide