Trapping Rain Water

LeetCode 42 • Hard • Arrays / Two Pointers

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] → Output: 6. Water at i = min(max_left, max_right) - height[i]. Two pointers move inward.

TimeO(n)

SpaceO(1)

left: — right: — water: 0

Left

Right

Water

left—

right—

water0

Speed:

Ready

Press Play. Two pointers: left and right. Water at current = min(maxL, maxR) - height. Move pointer at smaller max.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Two pointers: water = min(maxL, maxR) - height.

═══ TRAPPING RAIN WATER — TWO POINTERS ═══

PATTERN ▸ Two pointers (move smaller max) O(n) · O(1)

① INIT

left, right = 0, len(height)-1

maxL, maxR, water = 0, 0, 0

② LOOP WHILE left < right

if height[left] < height[right]:

water += max(0, maxL - height[left]); maxL = max(maxL, height[left]); left += 1

else: water += max(0, maxR - height[right]); maxR = max(maxR, height[right]); right -= 1

③ RETURN

return water

your implementation

Verify: