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

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

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 0
totalWater = 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

Logic walk through

while( l<=r ){if leftMax < rightMax 
if leftMax > height[l] calculate the water
else leftMax = height[l] //update leftMax

l++ //increment l
else //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).