Maximum Water Level at columni

As explained previously in the quote, now we can get the maximum water level at index/column i pretty easily. Before that, think about the values we currently have at hand on left[] and right[] arrays.

1left[i] = Maximum value of heights if we keep going to left from i.
2right[i] = Maximum value of heights if we keep going to right from i.

So what we need to do is get the minimum of these two to get the maximum water level at i. Remember, this is not yet what we want at each column/index. We want to have the amount of water at each column. So we subtract the height at i from the maximum level of water. That would be our desired value at each index.

1maxLevelOfWater[i] = Math.min(left[i], right[i]);
2water[i] = maxLevelOfWater[i] - height[i];

Finally, we can sum up the whole max_level_of_water array to get the final result. But do we really need another array max_level_of_water for this?

No, we don't! We can get the sum directly by calculating from left[] and right[] at each column and adding them (starting from 0) during the iteration. The modified pseudo code is below:

1let result = 0;
2for (let i = 0; i < n; i++) {
3    result += Math.min(left[i], right[i]) - height[i];
4}

To understand this, I am giving you the below diagram showing the values of an example at each step and arrays.

So the final solution is given below:

xxxxxxxxxx

console.log(totalRain(myArr));

function totalRain(heights){

  if (heights === null || heights.length <= 2) return 0;

​

  let N = heights.length;

  let max = 0;

  let left = new Array(N);

  let right = new Array(N);

​

  max = heights[0];

  left[0] = max;

  for (let i = 1; i < N; i++) {

    if (heights[i] > max) {

        max = heights[i];

    }

    left[i] = max;

  }

​

  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;

  }

​

  let result = 0;

  for (let i = 0; i < N; i++) {

    result += Math.min(left[i], right[i]) - heights[i];