Two Pointers · LC #42
Trapping Rain Water
Two-pointer approach: water at each cell = min(maxLeft, maxRight) − height. Process the side with the smaller boundary first - it is the bottleneck and its water is already determined.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given `n` non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining.
Sample I/O
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Input: height = [4,2,0,3,2,5] Output: 9
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
Water trapped at position i is bounded by the shorter of the tallest walls to its left and right: min(maxLeft[i], maxRight[i]) − height[i]. With two pointers, whichever side has the smaller max boundary is already fully constrained - we can compute its water contribution without knowing the other side's future.
Core Concept
Pointers l=0, r=n-1, maxL=0, maxR=0. While l < r: if height[l] <= height[r], process left side - if height[l] >= maxL update maxL, else add maxL - height[l] to water; advance l. Else process right side symmetrically; decrement r. Time O(n), Space O(1).
When to use
Any problem that asks for "trapped" or "bounded" water/area between heights. The two-pointer approach works when you can process each element once by comparing boundary maxima.
When NOT to use
When heights change dynamically (use a segment tree or Cartesian tree). When you need per-cell water values rather than just total (the DP approach is clearer).
Key Insights
What to Know Cold
- Key invariant: if height[l] <= height[r], the right side will always have a wall ≥ height[r] ≥ height[l] - so maxL is the binding constraint for the left pointer.
- The DP approach (precompute maxLeft[], maxRight[]) is O(n) time, O(n) space and is easier to reason about but uses extra memory.
- The stack-based approach finds "valleys" explicitly; same complexity, different mental model.
- Water at each bar cannot be negative - the max() with 0 is implicit since we only enter the water-addition branch when height < max.
- This problem tests ability to see through apparent O(n²) brute force to an O(n) two-pointer insight.
1 example
Worked Examples
Two-pointer water accumulation - Python
[0,1,0,2,1,0,1,3,2,1,2,1] → 6 units water trapped.
Process the smaller-boundary side; accumulate max - height when current < max.
def trap(height: list[int]) -> int:
l, r = 0, len(height) - 1
max_l = max_r = water = 0
while l < r:
if height[l] <= height[r]:
if height[l] >= max_l: max_l = height[l]
else: water += max_l - height[l]
l += 1
else:
if height[r] >= max_r: max_r = height[r]
else: water += max_r - height[r]
r -= 1
return water
# [0,1,0,2,1,0,1,3,2,1,2,1] → 6Output: 6
Canonical hard two-pointer problem; tests understanding of boundary invariants and appears frequently at FAANG on-sites.