LeetCode 42: Trapping Rain Water

Problem Restatement

We are given an array height.

Each value represents the height of a vertical bar. Every bar has width 1.

After rain falls, water can be trapped between taller bars. We need to compute the total amount of trapped water.

The official statement says: given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

The answer is:

6

Another example:

height = [4,2,0,3,2,5]

The answer is:

9

Input and Output

Function shape:

def trap(height: list[int]) -> int:
    ...

Key Observation

At any index i, water can stay above height[i] only if there is a wall on the left and a wall on the right.

The water level at index i is controlled by the shorter of the tallest left wall and the tallest right wall.

So the water above index i is:

min(max_left, max_right) - height[i]

If this value is negative, it contributes 0.

For example:

height = [0, 2, 0, 3]

At index 2, the height is 0.

The tallest wall on the left is 2.

The tallest wall on the right is 3.

The water level is limited by the shorter wall, which is 2.

So index 2 can hold:

2 - 0 = 2

units of water.

First Thought: Precompute Boundaries

A direct efficient solution is to precompute two arrays.

left_max[i] stores the tallest bar from index 0 to index i.

right_max[i] stores the tallest bar from index i to the end.

Then for each index i, the trapped water is:

min(left_max[i], right_max[i]) - height[i]

Code:

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)

        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        water = 0
        for i in range(n):
            water += min(left_max[i], right_max[i]) - height[i]

        return water

This solution is correct and runs in O(n) time.

The problem is that it uses O(n) extra space.

We can do better.

Key Insight

We do not need to store every left and right maximum.

We can keep two pointers:

left = 0
right = len(height) - 1

We also keep:

left_max = 0
right_max = 0

At each step, compare height[left] and height[right].

If height[left] < height[right], then the left side is the limiting side. There is already a right wall at least as tall as height[left], so the trapped water at left depends only on left_max.

If height[right] <= height[left], then the right side is the limiting side. There is already a left wall at least as tall as height[right], so the trapped water at right depends only on right_max.

This lets us process one side at a time.

Algorithm

Initialize:

left = 0
right = len(height) - 1
left_max = 0
right_max = 0
water = 0

While left < right:

If height[left] < height[right]:

1. Update left_max.
2. Add left_max - height[left].
3. Move left rightward.

Otherwise:

1. Update right_max.
2. Add right_max - height[right].
3. Move right leftward.

The update order matters.

We update the boundary maximum before adding water.

That guarantees we never add a negative amount.

Walkthrough

Use this input:

height = [4, 2, 0, 3, 2, 5]

Start:

left = 0
right = 5
left_max = 0
right_max = 0
water = 0

Since height[left] = 4 and height[right] = 5, process the left side.

At index 0, update:

left_max = 4

Water added:

4 - 4 = 0

Move left to index 1.

At index 1, height is 2.

The right side still has a wall of height 5, so the left boundary controls this position.

Water added:

4 - 2 = 2

Move left.

At index 2, height is 0.

Water added:

4 - 0 = 4

Move left.

At index 3, height is 3.

Water added:

4 - 3 = 1

Move left.

At index 4, height is 2.

Water added:

4 - 2 = 2

Total:

0 + 2 + 4 + 1 + 2 = 9

So the answer is:

9

Correctness

For each index, the trapped water depends on the smaller of the tallest wall on the left and the tallest wall on the right.

When height[left] < height[right], there is a right boundary that is taller than height[left]. Therefore, for the current left index, the amount of water is determined by the best left boundary seen so far, left_max.

If left_max is higher than height[left], the difference is trapped water. If not, the current bar becomes the new left boundary.

The same argument applies symmetrically when processing the right side.

Each step finalizes one index. Once an index is processed, its trapped water amount will not change, because the algorithm only processes a side when the opposite side already provides a sufficient boundary.

Therefore, every index contributes exactly the correct amount of trapped water, and the total sum is correct.

Complexity

Implementation

class Solution:
    def trap(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1

        left_max = 0
        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

Code Explanation

The two pointers begin at the ends of the array:

left = 0
right = len(height) - 1

The variables left_max and right_max store the best walls seen so far from each side.

left_max = 0
right_max = 0

The loop continues while there are unprocessed bars between the two pointers:

while left < right:

If the left bar is lower than the right bar, the left side is safe to process:

if height[left] < height[right]:

We update the best left wall:

left_max = max(left_max, height[left])

Then we add trapped water at this index:

water += left_max - height[left]

If the current bar is the tallest so far, this adds 0.

Otherwise, it adds the difference between the left boundary and the current height.

The right side is handled the same way:

right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1

At the end, water contains the total trapped rain water.

Testing

def run_tests():
    s = Solution()

    assert s.trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
    assert s.trap([4,2,0,3,2,5]) == 9
    assert s.trap([0]) == 0
    assert s.trap([0, 1, 2, 3]) == 0
    assert s.trap([3, 2, 1, 0]) == 0
    assert s.trap([2, 0, 2]) == 2
    assert s.trap([3, 0, 0, 2, 0, 4]) == 10

    print("all tests passed")

run_tests()