42. Trapping Rain Water.md

42. Trapping Rain Water (Hard)

[tag] two pointers

• use two opposite directional pointers to calculate max height for each direction
• use min of (max_left, max_right) - height for water difference at each location

class Solution:
    def trap(self, height: List[int]) -> int:
        max_height_left = [0] * len(height)
        max_height_right = [0] * len(height)
        ans = 0
        # find max-height array from left. 
        max_height = height[0]
        for i, num in enumerate(height):
            if num > max_height:
                max_height = num
            max_height_left[i] = max_height
        
        # find max-height array from left. 
        max_height = height[-1]
        for i in reversed(range(len(height))):
            if height[i] > max_height:
                max_height = height[i]
            max_height_right[i] = max_height
        # print(max_height_left)
        # print(max_height_right)
        for i, num in enumerate(height):
            ans += (min(max_height_left[i], max_height_right[i]) - height[i])
            # print(ans)
        return ans