Q24: Trapping Rain Water
Calculate how much water an elevation map can trap after raining using Two Pointers.
Two-Pointer Water Trapping
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;
}
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6💡 Maintains leftMax and rightMax bounds. Advances shorter pointer inward and adds trapped water based on difference between local max bound and bar height.
Key Takeaways
- Water trapped at any position is bounded by $\min(\text{maxLeft}, \text{maxRight}) - \text{height}[i]$.
- Two pointers allow tracking boundary bounds in O(n) time and O(1) space.
Knowledge Check
What determines the water level trapped above height[left] when height[left] < height[right]?