Trapping Rain Water

Patrick Leaton
Published: July 27, 2021, 7:45 a.m.
Problem Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

Constraints:

  • n == height.length
  • 0 <= n <= 3 * 10^4
  • 0 <= height[i] <= 10^5

 

 

The description was taken from https://leetcode.com/problems/trapping-rain-water/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
       
        left, right = 0, len(height)-1
        max_left, max_right = height[left], height[right]
        output = 0
       
        while left < right:
            if max_left < max_right:
                left += 1
                max_left = max(max_left, height[left])
                output += max_left - height[left]
            else:
                right -= 1
                max_right = max(max_right, height[right])
                output += max_right - height[right]
 
        return output
       

Problem Explanation

This problem is very similar to Container With the Most Water.

Similar to that problem, each container of water can only hold as much water as the minimum side can hold because water may escape from the smallest side of the container.

That means that a container is dependent on its minimum side.

With that being said, we can use two pointers and within each iteration, we see which side is the dependent side and we add water during that side and keep working inward.  Eventually, the greatest height of the map will be reached and the pointer that reaches that point first will stay there while the other continues filling water until the entire map is traversed.

We will start by checking if we have a map, to begin with.  If not, we can't hold any water so we will return zero.

        if not height:
            return 0

 

Then, we will create two pointers at each end of the map and two variables to track the maximum heights on each side so we can see which side is the dependent side later.

        left, right = 0, len(height)-1
        max_left, max_right = height[left], height[right]

 

We will also need an output variable to track how much water the map can hold.

        output = 0

 

Let's go ahead and draw this out since it will be hard to visualize otherwise.

Our map will begin like this:

                         
                                
                                               

 

We will have our pointers at both ends, and set the initial side maximums to each pointer.

 

Max L                      R  Max
                             
                                    
                                                        

 

We compare each side's maximum to see that the left is the dependent side so we can fill water on this side.  By moving the left pointer to the right and then testing the new height as the maximum before trying to add water, we can guarantee we don't have negative numbers.  Best case, the current index's height is lower than the previous left maximum so we can trap water here.  Worst case, the new index is now the left height maximum so subtracting it from itself will give us a zero value.

Right here, our left index is the new maximum so we can't trap water here.

 

Max   L                    R  Max
                               
                                      
                                                            

 

Next, we will compare the left and right maxes now to find the dependent side.  In this case, they are the same height so both are the dependent sides and we can choose to move either pointer.  We will move the right in these cases.

Again, the right pointer's height is the new maximum so we can't trap water here, we will add zero to the output.

 

Max   L                  R   Max
                               
                                          
                                                            

 

Now the left side is the dependent side. 

We will move the pointer and notice we now have an index that isn't the new maximum.  We can trap water here, we will add one to the output.

 

Max     L                 R   Max
                               
                                          
                                                              

 

The left side is still the dependent side, do the same thing. Now our index is the new left maximum, can't trap water here.

Max       L              R   Max
                               
                                                
                                                              

 

Both sides are dependent, move the right pointer.

The current index isn't the new right maximum, we can trap water here.  We will add one to the ouput.

Max       L            R     Max
                               
                                                
                                                              

 

Both sides are dependent again, let's move the right pointer.

The right index is still the new maximum.  We can't trap water here.

Max       L          R       Max
                               
                                                
                                                              

 

Both sides are dependent again, let's move the right pointer.

The right index is the new global maximum.  We can't trap water here.

Max       L        R         Max
                                   
                                                
                                                              

 

The right side is now the global maximum, left will continue to be the dependent side and the end result will look like this, six cells that were less than their dependent sides' local maximums.

Max                         Max
                                   
                                                      
                                                              

 

The coding for this solution is the simple part.

While both pointers haven't overlapped, we will compare both maximums to find the dependent side, move the dependent side's pointer and subtract the index's height from it's side's local maximum to get the value of water we can trap for that index.  Then, we will add that value to the output.

.  

        while left < right:
            if max_left < max_right:
                left += 1
                max_left = max(max_left, height[left])
                output += max_left - height[left]
            else:
                right -= 1
                max_right = max(max_right, height[right])
                output += max_right - height[right]

 

Once the pointers overlap, we will have done this calculation for each cell so we will output it.

        return output