[LC] 42. Trapping Rain WaterTech
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.
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
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 = ,  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)
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.