# LeetCode 42 Trapping Rain Water

— brute force, dynamic programming, two pointers

# Question

• An index can only trap water when there are bars (higher values)on both sides, so the first and last index can never trap water.
• It depends on the lower bar to decide how much water can be trapped.

# Brute Force

Since the first and last index can never trap water, we can iterate through the array from index `1` to index `arr.length-2`.

At each index `current`, we check the left side of the `current` index from index `0` to index `current-1` to find the maximum value `leftMax`.

And we check the right side of the current index from index `current+1` to index `arr.length-1` to find the maximum value `rightMax`.

Then we choose the smaller value between `leftMax` and `rightMax` to minus current value. If the difference is larger than 0, we can add it to the total amount of water.

## Code

`var trap = function(height) {    //start from index one to index height.length-2    //first and last index cannot trap water       let totalWater = 0        for(let cur = 1; cur < height.length-1; cur++){        //check left side of current index, and find the max value        let leftMax = 0        for(let i = cur-1; i >= 0; i--){           leftMax = height[i]>leftMax ? height[i]:leftMax        }                 //check right side of current index, and find the max value        let rightMax = 0        for(let i = cur+1; i < height.length; i++){            rightMax = height[i]>rightMax? height[i]:rightMax        }        //calculate water        let water = Math.min(leftMax, rightMax) - height[cur]        totalWater += water >0 ? water:0    }        return totalWater};`

Time complexity: O(n²). For each element of array, we iterate the left and right parts.

Space complexity: O(1).

## Test out:

` height  [0,1,0,2,1,0,1,3,2,1,2,1] index      1 2 3 4 5 6 7 8 9 10 leftMax    0 1 1 2 2 2 2 3 3 3 rightMax   3 3 3 3 3 3 3 2 2 1 min bar    0 1 1 2 2 2 2 2 2 1-valueOfInd 1 0 2 1 0 1 3 2 1 2  water      0 1 0 1 2 1 0 0 1 0 //if diff <0, water is 0 totalWater = 6           `

# Dynamic Programming

In brute force we figured out that we need to know the leftMax and rightMax for all the indexes. We can use dynamic programming and store them in arrays. We will set two arrays: `leftMax` and `rightMax`.

First, we set the first element in `leftMax` array to the first value in `height` for comparison later. Then we can iterate through `height`(from left to right), comparing `height[i-1]` and `leftMax[i-1]` to find the `leftMax` value for index `i` . Similar for `rightMax` array, but we start from index `height.length-1` (from right to the left).

Let’s see some tests first to help us understand:

## Test out

` index      0  1  2  3  4  5  6  7  8  9  10 11 height    [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]           --> leftMax   [0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3]                                            <-- rightMax  [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1] min bar    0  0  1  1  2  2  2  2  2  2  1  1-valueOfInd 0  1  0  2  1  0  1  3  2  1  2  1 water      0  0  1  0  1  2  1  0  0  1  0  0//if diff<0, water is 0totalWater = 6`

## Code

`var trap = function(height) {//use two arrays to track left and right max for each index    let leftMax = []    let rightMax = []    let totalWater = 0    //set first element of leftMax equals to first element in height for comparison later    leftMax = height    //same reason for the rightMax    rightMax[height.length-1] = height[height.length-1]        //fill the leftMax array    for(let i=1; i<height.length; i++ ){        leftMax[i] = leftMax[i-1]>height[i-1] ? leftMax[i-1] : height[i-1]    }        //fill the rightMax array    for(let i = height.length-2; i>=0; i--){        rightMax[i] = rightMax[i+1] > height[i+1]? rightMax[i+1] : height[i+1]    }//find the min of leftMax and rightMax for each index, and calculate the water amount    for(let i = 0 ; i < height.length; i++){        let water = Math.min(leftMax[i],rightMax[i]) - height[i]        totalWater+= water > 0 ? water : 0    }        return totalWater}`

Time complexity: O(n).
Space complexity: O(n).

## Two Pointer

We know from previous analysis that the lower bar decides how much water an index can trap. So we just have two pointers. One start from left `l` and another from right `r`. We would also need two variables to store the maximum value on left side `leftMax` and right side `rightMax`. When `leftMax` is smaller than `rightMax` , we know we can use `leftMax` to determine the water that can be trapped on the right side of the `leftMax` index.

## Logic walk through

`while( l<=r ){if leftMax < rightMax      if leftMax > height[l] calculate the water     else leftMax = height[l] //update leftMax         l++ //increment lelse //leftMax >= rightMax, rightMax is the lower bar     if rightMax > height[l] calculate the water     else rightMax = height[r] //update rightMax     r-- //decrease r}return total water`

## Code

`var trap = function(height) {  let l = 0  let r = height.length - 1    let leftMax = height[l]  let rightMax = height[r]    let totalWater = 0    while(l<=r){      if(leftMax<rightMax){          if(leftMax > height[l]){              totalWater+= leftMax - height[l]          }else{              leftMax = height[l]          }          l++      }else{          if(rightMax > height[r]){              totalWater+= rightMax - height[r]          }else{              rightMax = height[r]          }          r--      }        }        return totalWater};`

## Test out

` index      0  1  2  3  4  5  6  7  8  9  10 11 height    [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]l leftMax  r  rightMax leftMax<rightMax totalWater0    0    11     1          true            01    0    11     1          true            02    1    11     1          false           02    1    10     1          false           02    1    9      2          true            13    1    9      2          true            14    2    9      2          false           24    2    8      2          false           24    2    7      2          false           24    2    6      3          true            35    2    6      3          true            56    2    6      3          true            67    2    6      3          true            6`

Time complexity: O(n).
Space complexity: O(1).