42. Trapping Rain Water

class Solution:
    def trap(self, height: List[int]) -> int:
        """
        main idea: two pointers.  l, r move toward each other. get current l_max and r_max;
        then based on case, 1: l_max < r_max 2: r_max < l_max to get water at pos left/ right
        """
        # time O(N)  space O(1)
        if not height:return 0
        size = len(height)
        water =0
        l, r = 0, size -1
        # initialize l,r max height
        l_max, r_max = height[0],height[size-1]
        while l<=r:
            l_max = max(height[l],l_max)# update l_max
            r_max = max(height[r],r_max)# update r_max
            if l_max < r_max:
                water += l_max - height[l]
                l += 1
            else:
                water += r_max - height[r]
                r -=1
        return water