Trapping Rain Water

---

Intuition

• Naively, notice that in order to fill water into a space, the left and right of that space must contain that height. We can check for the left bar with the maximum height, and the right bar with the maximum height on each iteration. We know that we can fill to the minimum of those two on each index.
• Notice how we are repeating a lot of calculations with the naive approach. Therefore, use memoization and DP to store the sub-computations.
• This still takes extra space. Therefore, use two pointers. Notice that on each index, if the left bar with maximum height is less than the right bar with maximum height to the right, then the bottleneck is the left, and vice versa otherwise.

Complexity

Runtime

• $O(N)$

Space

• $O(1)$ with two pointers, $O(N)$ otherwise

Code

Two Pointers

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        water = 0
 
        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                if height[left] < left_max:
                    water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                if height[right] < right_max:
                    water += right_max - height[right]
                right -= 1
 
        return water

Memoization + DP

class Solution:
    def trap(self, height: List[int]) -> int:
        max_l = height[0]
 
        @cache
        def r(i):
            if i >= len(height):
                return -1
            return max(height[i], r(i + 1))
 
        water = 0
        for i in range(1, len(height) - 1):
            max_l = max(max_l, height[i - 1])
            max_r = r(i + 1)
            min_boundary = min(max_l, max_r)
            
            if height[i] < min_boundary:
                water += min_boundary - height[i]
            
        return water

TLE

class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        for i in range(1, len(height) - 1):
            max_l = max(height[:i])
            max_r = max(height[i + 1:])
            
            min_boundary = min(max_l, max_r)
            if height[i] < min_boundary:
                water += min_boundary - height[i]
        
        return water

Notes

• Google Drive:

Cards

START Basic Front: Trapping Rain Water Back: Check left and right boundaries END

---

References

• Trapping Rain Water