leetcode_42_solution_2.py

# This is the 2 pointer Solution/Approach
# It utilizes the fact that the amount of water a position
# can contain is bounded by the smallest wall to its left and right
# If the left < right, then we KNOW that it can contain whatever
# amount of water with respect to the height of the left wall (the smaller wall).
# and vice versa

def trap(self, height: List[int]) -> int:
    leftMax, rightMax, ans = 0, 0, 0
    left, right = 0, len(height)-1
    
    while left < right:
        if height[left] < height[right]:
            if height[left] < leftMax: # Can contain water
                ans += leftMax - height[left]
            else:
                leftMax = height[left]
            left += 1
        else: # height[right] >= height[left]
            if height[right] < rightMax: # Can contain water
                ans += rightMax - height[right]
            else:
                rightMax = height[right]
            right -= 1
    return ans