AlgoDaily - Trapping Rain Water

Mark As Completed Discussion

Do the same for right to left

We can do the exact same thing from right to left. This will be accumulated in a new array named right[].

So finally, we get the two arrays left[] and right[] that we can use to get the maximum water level at each column. See the code to understand how we got these two.

xxxxxxxxxx
console.log(totalRain(arr));
 
function totalRain(heights) {
    if (heights === null || heights.length <= 2)
        return 0;
​
    let N = heights.length;
    let max = 0;
    let left = Array(N).fill(0);
    let right = Array(N).fill(0);
​
    // scan from left to right
    max = heights[0];
    left[0] = max;
    for (let i = 1; i < N; i++) {
        if (heights[i] > max) {
            max = heights[i];
        }
        left[i] = max;
    }
    // scan from right to left
    max = heights[N - 1];
    right[N - 1] = max;
    for (let i = N - 2; i >= 0; i--) {
        if (heights[i] > max) {
            max = heights[i];
        }
        right[i] = max;
    }
    return right;
}