[LC] 42. Trapping Rain Water
TechGiven 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.