The amount of water that can be trapped at any single position is determined by the height of the "walls" to its left and right. Specifically, the water level is limited by the shorter of the two highest walls on either side.

The formula to calculate the water trapped at a single index i is: water[i] = min(max_left_height, max_right_height) - height[i]

If the result is negative, it means no water can be trapped at that position, so we take 0. The total amount of trapped water is the sum of the water trapped at each position.

The video explains an optimal solution with O(n) time complexity and O(1) space complexity using the two-pointer technique.

Initialize left and right pointers at the opposite ends of the array. Also, initialize leftMax and rightMax to track the maximum height encountered so far from each side, and a res variable to store the total trapped water.

if not height:
    return 0

l, r = 0, len(height) - 1
leftMax, rightMax = height[l], height[r]
res = 0

A while loop runs as long as l < r. Inside the loop, it compares leftMax and rightMax to decide which pointer to move.

• If leftMax is smaller, it's the bottleneck. The trapped water at the l position is calculated (leftMax - height[l]) and added to the result. The l pointer is then moved inward.
• Otherwise, rightMax is the bottleneck, and the same logic is applied to the r pointer.

while l < r:
    if leftMax < rightMax:
        l += 1
        leftMax = max(leftMax, height[l])
        res += leftMax - height[l]
    else:
        r -= 1
        rightMax = max(rightMax, height[r])
        res += rightMax - height[r]

After the loop finishes, the res variable contains the total trapped water.

return res

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

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res