Trapping Rain Water

Loading...LeetCode

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

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

Constraints:

• n == height.length

• 1 <= n <= 2 * 104

• 0 <= height[i] <= 105

You can solve this problem using the two-pointer approach. Here's a JavaScript implementation:

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

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                totalWater += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                totalWater += rightMax - height[right];
            }
            right--;
        }
    }

    return totalWater;
}

// Test cases
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // Output: 6
console.log(trap([4,2,0,3,2,5]));             // Output: 9

This implementation uses two pointers, left and right, which initially point to the start and end of the array, respectively. It also maintains leftMax and rightMax, representing the maximum height encountered from the left and right, respectively.

The algorithm then iterates through the array, moving the pointers towards each other until they meet. At each step, it calculates the water trapped between the current left and right pointers based on the difference between the current height and the corresponding maximum height encountered so far. Finally, it returns the total water trapped.