Optimal Python Solution for Trapping Rain Water (Interview Script)

2025-09-26

The Logic

• The bottleneck is avoiding nested scans for left and right maximums at every index.
• Use a two-pointer technique to maintain left and right boundaries in a single pass.
• Water trapped at an index is determined by the minimum of the two boundaries minus the current height.

Implementation / Diagram

Key Invariant

At every step, the side with the smaller boundary determines the trapped water because it is the limiting factor.

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water