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).