**Solution**

**Trapping Rain Water** https://leetcode.com/problems/trapping-rain-water/

- At height[i], what is the maximum height from [0, i-1] and [i+1, len(height)-1]? Let us call these heights as max_left and max_right.
- What is the water trapped at height[i]?

- if max_left <= height[i] or max_right <= height[i], then water trapped is 0
- if max_left > height[i] and max_right > height[i], then water_trap += min(max_left, max_right)-height[i]

- You can use linear space and precompute max_right. max_left can be computed as we move left to right.

```
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if height == []:
return 0
max_right = [-1]*len(height)
for i in range(len(height)-1, -1, -1):
max_right[i] = max(height[i], max_right[i+1]) if i < len(height)-1 else height[i]
water_trap, max_left = 0, height[0]
for i in range(1, len(height)-1):
h_left, h_right = max_left, max_right[i+1]
if h_left > height[i] and h_right > height[i]:
water_trap += min(h_left,h_right) - height[i]
max_left = max(max_left, height[i])
return water_trap
```