[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.