leetcode_42_solution_1.py

# This is the Dynamic Programming Solution/Approach
# Find the tallest left and tallest right for each index, then solve for the
# water each position will add to the total.

def trap(self, height: List[int]) -> int:
    maxLefts, maxRights = [0] * len(height), [0] * len(height)
    
    # init values
    maxLefts[0] = height[0]
    maxRights[len(height)-1] = height[len(height)-1]
    
    i, j = 1, len(height)-2
    while i < len(height):
        maxLefts[i] = max(maxLefts[i-1], height[i]) # Check this height to max height to left
        maxRights[j] = max(maxRights[j+1], height[j]) # Check this height to max height to right
        
        i += 1
        j -= 1
        
    # Determine answer
    ans = 0
    for i in range(0, len(height)):
        ans += max(0, min(maxLefts[i], maxRights[i]) - height[i])
    
    return ans