LeetCode 42 · Hard · Two Pointers

Trapping Rain Water

Each value in height is a bar of width 1. After rain, water pools between taller bars. Return how many units of water stay trapped.

O(n)time
O(1)space
min(leftMax, rightMax)sets each column's level

1–16 integers, 0 to 12

Legend grey bars = height (bold number, index below) · blue = trapped water, +n under each column · dashed lines = leftMax over [0..l] and rightMax over [r..end]; solid = the lower one, which decides

public int trap(int[] height) { if (height.length == 0) { return 0; } int l = 0; int r = height.length - 1; int leftMax = height[l]; int rightMax = height[r]; int res = 0; while (l < r) { if (leftMax < rightMax) { l++; leftMax = Math.max(leftMax, height[l]); res += leftMax - height[l]; } else { r--; rightMax = Math.max(rightMax, height[r]); res += rightMax - height[r]; } } return res;}
l
—
r
—
leftMax
—
rightMax
—
res
0

Why it works

  1. Brute force scans both sides for every column: the water over i is min(max left of i, max right of i) − height[i]. Finding both maxima per column is O(n²). Precomputing two max arrays makes it O(n) time but O(n) space.
  2. The lower side decides. If leftMax < rightMax, some bar on the right is at least rightMax tall, so the water over the next left column is capped by leftMax alone, whatever lies in between. Settle that column and move l. The mirror case moves r.
  3. Why O(n) and O(1): each step settles one column for good and moves one pointer inward. Two maxima and the total are all the state.
  4. Pitfall: update the max before adding water. Then leftMax − height[l] is never negative: a new tallest bar holds 0 water instead of a negative amount.
  5. Equal maxima: moving either side is fine. Both caps are the same height, so the lower-side argument holds either way.
  6. Related: Container With Most Water picks one pair of walls; here every column gets its own level. A monotonic stack also solves this in O(n), filling basins layer by layer.