Two Pointer Optimization — Less Than Naive

Two pointers often reduce O(n^2) nested loops to O(n) by proving you can skip inner resets—monotone structure is key.

Try this in Python

def trap_rain_water(heights: list[int]) -> int:
    """Classic two ends toward center (pedagogy stub — real solution uses two pointers)."""
    if not heights:
        return 0
    left, right = 0, len(heights) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if heights[left] < heights[right]:
            left_max = max(left_max, heights[left])
            water += max(0, left_max - heights[left])
            left += 1
        else:
            right_max = max(right_max, heights[right])
            water += max(0, right_max - heights[right])
            right -= 1
    return water


print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Key takeaways

• Rain water is a famous two-pointer optimization story.
• Always move the side with smaller bound.
• Prove you never miss trapped units.