Optimization — naive-ஐ விட சிறப்பு

Nested O(n^2) → O(n): inner reset skip — monotone structure முக்கியம்.

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 — famous story.
• சிறிய bound side நகர்த்தல்.
• Proof intuition.