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

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