30. Trapping Rain Water

Difficulty:HardPattern:Two Pointers / Boundary MaxTime:O(n)Space:O(1)

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.

How It Works & Algorithmic Design

Solves using Two Pointers Inward Traversal:

Pointers & Max Tracks: left = 0, right = height.length - 1, leftMax = 0, rightMax = 0, totalWater = 0.
Converging Loop (While left < right):
- If height[left] < height[right]:
  - If height[left] >= leftMax, update leftMax = height[left].
  - Else, accumulate trapped water: totalWater += leftMax - height[left].
  - Increment left++.
- Else:
  - If height[right] >= rightMax, update rightMax = height[right].
  - Else, accumulate trapped water: totalWater += rightMax - height[right].
  - Decrement right--.
Return: totalWater.

Why This Approach Works Best

Water trapping depends on Math.min(leftMax, rightMax) - currentHeight. Moving the smaller height pointer guarantees correct water boundary calculations in single-pass linear $O(n)$ time and $O(1)$ space.

Example Walkthrough

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Elevation bar graph.

Trapped Water Sum: 1 unit at idx 2 + 1 at idx 4 + 2 at idx 5 + 1 at idx 6 + 1 at idx 9 = 6 units

Calculates trapped water volume.

Output: 6

Total trapped rain water units.

Answer: Trapping Rain Water using Two Pointers

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0, totalWater = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) leftMax = height[left];
      else totalWater += leftMax - height[left];
      left++;
    } else {
      if (height[right] >= rightMax) rightMax = height[right];
      else totalWater += rightMax - height[right];
      right--;
    }
  }
  return totalWater;
}

💡 Track leftMax and rightMax while moving inward from the shorter boundary.

Key Takeaways

Water level at any bar is bounded by min(leftMax, rightMax) - barHeight.
Moving the shorter pointer ensures the smaller maximum boundary is known.
Single-pass solution achieving linear $O(n)$ time and $O(1)$ space.