Trapping Rain Water (Two Pointers)

Use the two-pointer technique to compute total trapped rainwater between elevation bars.

two-pointers arrays water-trapping interview

Write a function `trapped_rain_water(heights)` that takes a list of non-negative integers `heights` (each representing the height of a bar of width 1) and returns the total amount of water that can be trapped after rain.

Use the two-pointer approach: maintain left and right pointers, track the maximum height seen from the left and from the right, and move the pointer with the smaller boundary inward, adding trapped water when the current height is less than the max on that side.

- The input list may be empty or have fewer than 3 elements; in such cases, no water can be trapped, so return 0.
- Heights are non-negative integers (0 is allowed).

Constraints

0 ≤ len(heights) ≤ 10^5
0 ≤ heights[i] ≤ 10^5
Time complexity: O(n), Space complexity: O(1) (excluding output).

Example

>>> trapped_rain_water([0,1,0,2,1,0,1,3,2,1,2,1])
6
>>> trapped_rain_water([4,2,0,3,2,5])
9
>>> trapped_rain_water([1,2,3])
0
>>> trapped_rain_water([])
0

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the water trapped at a position as min(max_left, max_right) - height[pos].

You can compute trapped water in a single pass by moving the pointer with the smaller current boundary.

If heights has fewer than 3 elements, the answer is automatically 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.