# Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

```Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6```

Discussion

We can approach this problem in two ways. One is to find the different shapes and calculate the area filled in by the shapes. The other is to look at how much water is on top of each pillar.
If this was a graph question with a 2D matrix, we may use the first method (and sometimes have to). However in this case, the second method of looking at each pillar separately makes more sense since it makes the calculation easier.
The height of the pillar plus the water for each pillar is the minimum of the tallest pillars on the left and right sides. Any water above that would spill over. Then we just subtract the height of the pillar itself (since the pillar isn’t hollow and therefore displaces water).
Height = min(tallest pillar to the left, tallest pillar to the right)
Water = Height – PillarSize

Approach – Dynamic Programming

We don’t need to recalculate/recheck all the pillars to the left and right of the current pillar for each iteration of our main loop. Let’s think about this for a second.
At each pillar, the max pillar length to the left of the current one is the larger of the pillar directly to the left and the max of all the pillars to the left of that.
We create two cache objects. One for keeping track of the max pillar size to the left of the index, and one for keeping track of the max pillar size to the right of the index.
We populate these caches from left to right for the left pillar and right to left for the right pillar. So we create that initial loop to populate the caches. This takes O(N) time and O(N) space.
Now we use the cache objects and our formula (see Discussion section) to calculate how much water is held above the current pillar for each pillar in the input. The total of all the water is our final result, which we return.

``````var trap = function(height) {
const cacheRight=[];
const cacheLeft=[];

//populate cache
for (let i=0;i<height.length;i++) {
//left cache
cacheLeft[i]=Math.max(cacheLeft[i-1] || 0,height[i]);
//right cache
cacheRight[height.length-i-1]=Math.max(cacheRight[height.length-i-1+1] || 0,height[height.length-i-1]);
}
//process result
let result=0;
for (let i=0;i<height.length;i++) {
const wheight=Math.min(cacheRight[i],cacheLeft[i])-height[i];
result=result+wheight;
}
return result;
};``````