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