[LC] 42. Trapping Rain Water

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.
Constraints:
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

Approach

I was solving this problem at least three times and I think the greedy approach is one of the most convenient ways. I remember there is a two-pointer approach but I actually don’t like it especially a short period of time. But it’s obvious that two pointer approach is always efficient.

In my approach, I set the w[i] = min(highest_left[i] + highest_right[i]) – height[i] because at point of “i”, we can simply find minimum height between highest so far from both left and right. Then, subtract with height[i] will return the level of water. Of course, we should ignore if that level is negative.

class Solution:
    def trap(self, height: List[int]) -> int:
        highest_left, highest_right = [0], [0]
        n = len(height)
        
        for i in range(1, n):
            highest_left.append(max(highest_left[i-1], height[i-1]))
            highest_right.append(max(highest_right[i-1], height[n-i]))
        
        
        t = 0
        for i in range(1,n-1):
            w = min(highest_left[i], highest_right[n-i]) - height[i]
            t += 0 if w<0 else w
        return t

Time/Space Complexity: O(N)

Submission

Runtime: 60 ms, faster than 42.17% of Python3 online submissions for Trapping Rain Water.
Memory Usage: 15.2 MB, less than 7.36% of Python3 online submissions for Trapping Rain Water.