# [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:6Explanation: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 * 10`

^{4}`0 <= height[i] <= 10`

^{5}

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