LeetCode 42 · Two Pointers · Dynamic Programming

Trapping Rain Water

HardSum the water trapped between bars — two pointers, O(1) space.
Given an array height representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Walkthrough

try:
Water above each bar is capped by the shorter of the tallest walls to its left and right.
0L1234567891011R
leftMax0rightMax0water0
pointerwater
1
function trap(height) {
2
  let left = 0, right = height.length - 1;
◄
3
  let leftMax = 0, rightMax = 0;
4
  let water = 0;
5
  while (left < right) {
6
    if (height[left] < height[right]) {
7
      leftMax = Math.max(leftMax, height[left]);
8
      water += leftMax - height[left];
9
      left++;
10
    } else {
11
      rightMax = Math.max(rightMax, height[right]);
12
      water += rightMax - height[right];
13
      right--;
14
    }
15
  }
16
  return water;
17
}
left = 0right = 11
step 0 / 47
line 2
Pointers at both ends
Walk inward from both sides.

Intuition

Water above a bar is limited by the tallest wall to its left and the tallest to its right: trapped = min(leftMax, rightMax) − height[i].

Use two pointers with running maxima leftMax and rightMax. The clever part: whichever side currently has the SHORTER wall is the binding constraint, so that column’s water is fully determined right now.

If height[left] < height[right], then leftMax is guaranteed ≤ rightMax for the left column, so add leftMax − height[left] and move left inward. Otherwise do the mirror on the right.

This resolves one column per step in a single pass — O(n) time and O(1) space, no prefix arrays needed.

The algorithm

  1. 01Put left at 0 and right at the end; track leftMax, rightMax, and total water.
  2. 02Compare height[left] and height[right]; work on the shorter side.
  3. 03Update that side’s running max, add (max − height) to water, and step that pointer inward.
  4. 04Repeat until the pointers meet; return the total.

Reference implementation

1
function trap(height) {
2
  let left = 0, right = height.length - 1;
3
  let leftMax = 0, rightMax = 0, water = 0;
4
  while (left < right) {
5
    if (height[left] < height[right]) {
6
      leftMax = Math.max(leftMax, height[left]);
7
      water += leftMax - height[left];
8
      left++;
9
    } else {
10
      rightMax = Math.max(rightMax, height[right]);
11
      water += rightMax - height[right];
12
      right--;
13
    }
14
  }
15
  return water;
16
}

Complexity

Time
O(n) — single pass.
Space
O(1).