Trapping rain water

Hard TimeO(n) SpaceO(1)

Each value in height is a bar one unit wide, together making an elevation map. After rain, water settles in the dips: above any position it fills to the lower of the tallest bar on its left and the tallest on its right, minus that position's own bar. Nothing is trapped past either end, and heights are zero or greater. Return how many units are trapped in total.

Examples

Example 1

Input
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output
6
1 unit over index 2, 1 over index 4, 2 over index 5, 1 over index 6 and 1 over index 9.

Example 2

Input
height = [3, 2, 1]
Output
0
Descending all the way, so no position has a taller bar on its right to hold anything in.

The Code

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

The first 11 calls, of 13. This one does not fit on a page.

Step through trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) call by call

More like this

All two pointers examples (9) →