{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Trapping Rain Water – Solution & Complexity

Interview solutions
/
Trapping Rain Water

Watch: Trapping Rain Water with two pointers

Water above a bar is min(tallest on the left, tallest on the right) − its height. Prefix and suffix max arrays give that in O(n) space. Two pointers do it in O(1): always process the side with the lower max, because that side's water level is already known.

Solution Walkthrough

  1. Step 1: Understand What Water Needs

    • Water above an index is limited by the tallest wall on its left and the tallest wall on its right.
    • If the shorter of those two walls is taller than the current bar, the difference is trapped water.
    • Bars at the ends cannot trap water because one side is open.

  2. Step 2: Start with Prefix and Suffix Maximums

    • A direct dynamic programming solution precomputes left_max[i] and right_max[i].
    • Then each index contributes min(left_max[i], right_max[i]) - height[i] if that value is positive.
    • This is correct but uses O(n) extra space.
    def trap(height: list[int]) -> int:
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    # Fill both arrays, then sum the water at each index.

  3. Step 3: Use the Two-Pointer Insight

    • We can avoid the extra arrays by scanning from both ends.
    • Whichever side has the smaller current maximum is the limiting side for that step.
    • If left_max <= right_max, the left position's water is already determined; otherwise the right position's water is determined.

  4. Step 4: Accumulate Water While Moving Inward

    • Keep left, right, left_max, and right_max.
    • Update the maximum for the side you move.
    • If the current bar is lower than that side's maximum, add the difference to the answer.
    def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 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

  5. Step 5: Final Complete Solution

    • This version handles empty or very small arrays naturally because the loop does not run.
    • Each bar is visited at most once.
    • Time complexity is O(n), and extra space complexity is O(1).
    def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water
Learn the Two Pointers pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Trapping Rain Water online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Best Time to Buy and Sell Stock solution (easy)Coin Change solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?