42. Trapping Rain Water

Array Two Pointers Dynamic Programming Stack

Given n non-negative bar heights of width 1, compute how much rain water is trapped between the bars after raining.

Move inward from both ends, always on the side with the lower max. That side's water is bounded by its own max, since the other side is known to be at least as tall.

1function trap(height: number[]): number {
2  let l = 0, r = height.length - 1, lMax = 0, rMax = 0, water = 0;
3  while (l < r) {
4    lMax = Math.max(lMax, height[l]); rMax = Math.max(rMax, height[r]);
5    if (lMax < rMax) water += lMax - height[l++];
6    else water += rMax - height[r--];
7  }
8  return water;
9}

lMax = 0rMax = 0water = 0

height

water above bar

Pointers at both ends.

1 / 0

Space: play/pause · ←/→: step