42. Trapping Rain Water using JavaScript

Problem

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

Solution

First attempt : Stack method

/**
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {
    let water = 0;
    let stack = [];
    
    for (let current = 0; current < height.length; current++) {
    while(stack.length != 0 && height[current] > height[stack[stack.length - 1]]){
        let top = stack.pop();
        if(stack.length === 0){
            break;
        }
        let distance = current - stack[stack.length - 1] - 1;
        let bounded_height = Math.min(height[current], height[stack[stack.length - 1]]) - height[top];
        water += distance * bounded_height;
    }
    stack.push(current);
    }
    return water;
}

Second attempt : Two pointer method

/**
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {
    let left = 0, right = height.length - 1;
    let maxLeft = 0, maxRight = 0;
    let water = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= maxLeft) {
                maxLeft = height[left];
            } else {
                water += maxLeft - height[left];
            }
            left++;
        } else {
            if (height[right] >= maxRight) {
                maxRight = height[right];
            } else {
                water += maxRight - height[right];
            }
            right--;
        }
    }
    return water;
}