loading

42. Trapping Rain Water — Step-by-Step Visualization

hardLeetCode #42ArrayTwo PointersDynamic ProgrammingStack

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`

Algorithm Pattern

Two Pointers / Prefix Maximums

Key Idea

The water trapped at index `i` is determined by `min(leftMax[i], rightMax[i]) - height[i]`. We can calculate this in `O(1)` space by moving two pointers from the ends inward and maintaining current `leftMax` and `rightMax`.

Step-by-Step Approach

  1. Initialize `l = 0` and `r = height.length - 1`.
  2. Maintain `leftMax = height[l]` and `rightMax = height[r]`.
  3. While `l < r`, compare `leftMax` and `rightMax`.
  4. If `leftMax < rightMax`, move the left pointer `l` inward, update `leftMax`, and add `leftMax - height[l]` to the total.
  5. If `rightMax <= leftMax`, move the right pointer `r` inward, update `rightMax`, and add `rightMax - height[r]` to the total.

Common Gotchas

  • Only the pointer corresponding to the smaller maximum moves—this is because the smaller wall is the bottleneck limiting the water level at that index.
  • Empty or flat maps trap no water.

Related Problems

← All problems