Trapping Rain Water – Solution & Complexity

Q: What is the time and space complexity of Trapping Rain Water?

The optimal Trapping Rain Water solution runs in `O(n)` time and `O(1)` space. Two pointers with running left/right maxima decide the trapped water at each step.

Q: What is the most efficient way to solve Trapping Rain Water?

Two pointers with running left/right maxima decide the trapped water at each step. This gives `O(n)` time complexity, and is a classic arrays, two pointers, stack, and dynamic programming problem.

Q: How do you solve Trapping Rain Water in Python & JavaScript?

We provide a worked Trapping Rain Water solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Trapping Rain Water an easy or hard interview question?

Trapping Rain Water is generally rated **Hard**. It tests arrays, two pointers, stack, and dynamic programming, which are common coding-interview patterns.

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. 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. 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. 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. 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

Trapping Rain Water – Solution & Complexity

1. Understand What Water Needs

2. Start with Prefix and Suffix Maximums

3. Use the Two-Pointer Insight

4. Accumulate Water While Moving Inward

5. Final Complete Solution

FAQ

What is the time and space complexity of Trapping Rain Water?

What is the most efficient way to solve Trapping Rain Water?

How do you solve Trapping Rain Water in Python & JavaScript?

Is Trapping Rain Water an easy or hard interview question?