# 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[0] = height[0] //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 totalWater

0 0 11 1 true 0

1 0 11 1 true 0

2 1 11 1 false 0

2 1 10 1 false 0

2 1 9 2 true 1

3 1 9 2 true 1

4 2 9 2 false 2

4 2 8 2 false 2

4 2 7 2 false 2

4 2 6 3 true 3

5 2 6 3 true 5

6 2 6 3 true 6

7 2 6 3 true 6

Time complexity: O(n).

Space complexity: O(1).