class Solution:
    def trap(self, height: List[int]) -> int:

        # # Solution-1: DP with O(2n) = O(n)
        # # edge case handling
        # if not height: return 0
        
        # # DP to calculate leftMax and rightMax
        # leftMax = [0] * len(height)
        # leftMax[0] = height[0]
        # for i in range(1,len(height)):
        #     leftMax[i] = max(leftMax[i-1], height[i])
        
        # rightMax = [0] * len(height)
        # rightMax[-1] = height[-1]
        # for i in range(len(height)-2,-1,-1):
        #     rightMax[i] = max(rightMax[i+1], height[i])
        
        # # find the max
        # res = 0
        # for i in range(len(height)):
        #     res += min(rightMax[i], leftMax[i]) - height[i]
        # return res



        # Solution-2: two-pointer with O(n)

        if not height: return 0

        leftMax = 0
        rightMax = 0
        l = 0
        r = len(height) - 1
        res = 0
        while l <= r:


            if leftMax <= rightMax:

                res += max(0, leftMax - height[l])
                
                leftMax = max(leftMax, height[l])
                l += 1
            
            else:

                res += max(0, rightMax - height[r])
                
                rightMax = max(rightMax, height[r])
                r -= 1
        
        return res