As usual, we'll solve this by examining some test cases to get a feel for the varying scenarios. After we've developed an intuition, we can try to identify a pattern towards a solution.

The previous image shows that we can only trap water if there is a valley-like pattern in the elevation map, meaning a low area between higher areas. So we want to find a segment where the shape is as follows: the height of the bars have a decrease, followed by an increase in height, to "catch" the rain.

Let's also look at a few maps which don't trap any water.

Solving the Problem

We can come up with several methods of computing the amount of rainwater trapped by an elevation map. We should always start by brute forcing it, and ask ourselves how we'd manually determine the result we want.

Let's take a super simple example, [5, 3, 5]. Picture it below:

1X R X
2X R X
3X X X
4X X X
5X X X
65 3 5
7
80 1 2   <-- index

Well, starting at the first element 5, we know that no rain can be trapped. So we move on. At the second element, 3, things get interesting: we know based on our observation of the element before it, it can carry up to 2 extra units of rain. Because the element that follows is also a 5, it makes sense that that shape can hold 2.

But suppose one of the surrounding hills was 6 instead:

1    X
2X R X
3X R X
4X X X
5X X X
6X X X
75 3 6
8
90 1 2   <-- index

Any rain that would reach 5 units worth can be pictured as "sliding off" the elements at index 0 and 1. So at every element, we actually want to find the two highest peaks surrounding said element, and take the second highest.

So that's the brute force solution. Here, let's see this visually: we'll discuss one simple but efficient way to calculate the result.

All we need is to determine what the maximum water level can be at each column of the whole map. To get this, read and understand the below statement very carefully, and think about it:

The maximum level of water at index i is the minimum value of the maximum heights in both directions from i. water_level(i) = min(max_height[0:i-1], max_height[i+1:n])

After determining the maximum level of water, we can just subtract the height at i from the maximum level of water to get the water height at i.

Now we need to solve how to get the maximum water levels. Believe it or not, it's already been solved by the quote I gave you earlier. Do you see it?

Here it is: we need to get the maximum height from both sides of i (left and right) to get the maximum water level at i. What if we can divide the problem into two similar problems with different directions? We can do this with two new arrays. See the image below:

First, we go from left to right and keep the maximum height found until now in a new array. Think of it as a running max height from the left.

xxxxxxxxxx

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 = 0; i < N; i++) {

        if (heights[i] > max) {

            max = heights[i];

        }

        left[i] = max;

    }

​

    return left;

}

​

// uncomment a different array to see the working on a different array

// let arr = [0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0]; // should be 6

// let arr = [0, 0, 1, 0, 2, 4, 4, 4, 2, 3, 1, 0, 2, 4, 3, 1, 0, 1]; // should be 14

// let arr = [0, 0, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0]; // should be 0

let arr = [ 5, 1, 2, 4, 4, 4, 3, 1, 0, 0, 0 ]; // should be 5

​

console.log(totalRain(arr));