Senior · Two pointers

Trapping Rain Water

Given nonnegative integer bar heights of unit width, return the total trapped water. Empty input traps 0. Explain why the smaller boundary determines a safe amount to accumulate.

Examples

[4,2,0,3,2,5] → 9

Compare approaches

Scan both boundaries per bar

Water above each bar is bounded by the shorter of the tallest left and right walls.

Time: O(n²) · Space: O(1)

function trappedWater(heights) { let total = 0; for (let i = 0; i < heights.length; i++) { let left = 0, right = 0; for (let j = 0; j <= i; j++) left = Math.max(left, heights[j]); for (let j = i; j < heights.length; j++) right = Math.max(right, heights[j]); total += Math.min(left, right) - heights[i]; } return total; }

Two running boundaries

Advance the side with the smaller known maximum. The other side already supplies a sufficient boundary for that position.

Time: O(n) · Space: O(1)

function trappedWater(heights) {
  let left = 0, right = heights.length - 1, leftMax = 0, rightMax = 0, total = 0;
  while (left <= right) {
    if (leftMax <= rightMax) {
      leftMax = Math.max(leftMax, heights[left]);
      total += leftMax - heights[left++];
    } else {
      rightMax = Math.max(rightMax, heights[right]);
      total += rightMax - heights[right--];
    }
  }
  return total;
}

Common traps

An empty array must not read a nonexistent bar.
Summing adjacent dips misses wide basins.

Practise in the workspace →