Trapping Rain Water

Examples

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

Water pools above the low spots wherever there are taller bars on both sides; adding up the water trapped at every position gives 6 total units.

Input: height = [4, 2, 0, 3, 2, 5]
Output: 9

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

The elevation only ever rises, so there's never a wall on both sides of a low spot — nothing gets trapped.

Constraints

• 1 <= height.length <= 2 * 10^5

• 0 <= height[i] <= 10^5

Approach

The amount of water that can sit above any single bar is determined by the shorter of the tallest bar to its left and the tallest bar to its right — whichever side is shorter is where the water would spill out first. A direct approach recomputes those two values by scanning outward from every position, which repeats a lot of work.

A better approach precomputes the tallest-bar-so-far from the left and from the right in two passes, storing them in two arrays, and then combines them in a third pass — fast, but it uses extra memory proportional to the input.

The optimal approach avoids storing those arrays at all. Walk two pointers inward from both ends, keeping a running "tallest seen so far" for each side. At every step, you always know for certain that the smaller of the two running maximums is the true limiting wall for whichever pointer is behind, which is enough information to compute that position's trapped water immediately and move that pointer inward.

Solutions

Brute Force — Scan Left and Right From Every Bar

For each position, scan all the way left to find the tallest bar so far, and all the way right to find the tallest bar so far, then use the shorter of the two to work out how much water sits there.

function trap(height) {
  let total = 0;
  const n = height.length;

  for (let i = 0; i < n; i++) {
    let leftMax = 0;
    for (let l = 0; l <= i; l++) leftMax = Math.max(leftMax, height[l]);

    let rightMax = 0;
    for (let r = i; r < n; r++) rightMax = Math.max(rightMax, height[r]);

    total += Math.min(leftMax, rightMax) - height[i];
  }

  return total;
}

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

Better — Precomputed Left/Right Max Arrays

Precompute, in one left-to-right pass, the tallest bar seen so far up to each position, and in one right-to-left pass, the tallest bar seen so far from each position onward. Then a final pass combines them.

function trap(height) {
  const n = height.length;
  if (n === 0) return 0;

  const leftMax = new Array(n);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  }

  const rightMax = new Array(n);
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  }

  let total = 0;
  for (let i = 0; i < n; i++) {
    total += Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return total;
}

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

Optimal — Two Pointers

Walk two pointers inward from both ends, tracking a running maximum height seen on each side. Whichever side currently has the smaller running maximum is the one you can safely resolve next — its running maximum is guaranteed to be the true limiting wall for that position.

function trap(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let total = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      total += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      total += rightMax - height[right];
      right--;
    }
  }

  return total;
}

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