Trapping rain water in javascript

Learn how to solve the trapping rain water problem in javascript.

The problem statement is read as given an array of non-negative integers representing the elevation wall calculate the amount of rain water that can trapped inside it.

Example

Input:
[0,1,0,2,1,0,1,3,2,1,2,1]

Output:
6

We are going to see two different solutions.

1. Naive using brute force.
2. An efficient approach.

Naive approach using brute force.

Conceptually it works as follows:

• If there is greater wall then there is potential that water can be stored.
• So calculate the amount of water that can be stored.
• While doing this keep track of the longest wall. Because it will help to calculate the rain water that can be stored above the current.

const trap = (height) => {

    let largest = height[0];
    let largestIndex = 0;
    let water = 0;

    for(let i=1; i height[i-1]) {
            
            // what is the max water level
            let fill = Math.min(largest, height[i]);
            
            // fill in the water between largest and i
            for(let j=largestIndex+1; j largest) {
                largest = height[i];
                largestIndex = i;
            }
            
        }
        
    }
    return water;
};

Input:
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

Output:
6

Time complexity: O(n ^ 2).

Space complexity: O(1).

An efficient approach to find the trapping rain water in javascript.

• In this approach we start calculating the water trapped from both the ends and then combine them together to return the total.
• If the right wall is greater the left walls then calculate the amount of water that could be stored there and move further.

const trap = (height) => {
    let leftMax = -1, 
        rightMax = -1, 
        left = 0, 
        right = height.length - 1, 
        water = 0;
  
    while (left <= right) {
        //Get the max wall height from both the ends
        leftMax = height[left] > leftMax ? height[left] : leftMax
        rightMax = height[right] > rightMax? height[right] : rightMax
        
        //calculate the amount of water trapped
        if (leftMax > rightMax) {
            water += rightMax - height[right]
            right--
        }
        else {
            water += leftMax - height[left]
            left++
        }
    }
  
    return water
};

Input:
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));

Output:
6

Time complexity: O(n).

Space complexity: O(1).