[42. Trapping Rain Water] #leetcode

42_1019.py

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # return placeholder
        res = 0
        
        # corner case
        if not height or len(height) <= 2:
            return res
        
        # initialize data
        left, right, leftmax, rightmax = 0, len(height) - 1, 0, 0
        
        # two points from left and from right respectively
        while left <= right:
          # find the left or right bound and get the trapped water
            if leftmax <= rightmax:
                res += max(leftmax - height[left], 0) 
                leftmax = max(leftmax, height[left])
                left += 1
            else:
                res += max(rightmax - height[right], 0)
                rightmax = max(rightmax, height[right])
                right -= 1
            # print("{} {} {} {} {}".format(left, right, leftmax, rightmax, res))
            
        # return 
        return res