class Solution:
    def trap(self, height: List[int]) -> int:
        #Three time line scanning
        #TC: O(len(height))
        #SC: O(len(height))

        n = len(height)

        if n <= 2:
            return 0

        Leftmost = [-1]*n
        LeftMax = height[0]
        for i in range(1, n):
            LeftMax = max(LeftMax, height[i-1])
            Leftmost[i] = LeftMax - height[i]

        Rightmost = [-1]*n        
        RightMax = height[-1]
        for i in range(n-2, -1,-1):
            RightMax = max(RightMax, height[i+1])
            Rightmost[i] = RightMax - height[i]

        res = 0
        for i in range(1,n-1):
            res += max(min(Leftmost[i], Rightmost[i]),0)

        return res