LeetEye LeetEye
Easy Two Pointers ~5 min

Trapping Rain Water

two-pointers trapping-rain-water

Problem

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.

Examples

Example 1
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
The elevation map (black) can trap 6 units of rain water (blue).
Example 2
Input: height = [4,2,0,3,2,5]
Output: 9
Key Insight

Water at position i = min(max_left, max_right) - height[i]

Water at each position = min(max_left, max_right) - height. Two pointers let us compute this in O(1) space by always processing the side with the smaller known max.

How to Approach This Problem

Pattern Recognition: When you see keywords like trapping rain water two-pointers, think Two Pointers.

Step-by-Step Reasoning

1 Water can be trapped at position i if:
Answer: There's a taller bar somewhere to the left AND somewhere to the right
Water needs walls on both sides to be contained. Without both, it would flow off.
2 The water level at position i cannot exceed:
Answer: min(tallest left, tallest right)
Water would overflow over the shorter of the two bounding walls.
3 If max_left = 3, max_right = 2, height[i] = 1, water trapped = ?
Answer: 2 - 1 = 1
Water level = min(3, 2) = 2. Water trapped = 2 - 1 = 1.
4 Naive approach: For each position, scan left for max, scan right for max. Time complexity?
Answer: O(n²)
For each of n positions, we scan up to n elements left and right.
5 We can precompute max_left[] and max_right[] arrays. What's the new time complexity?
Answer: O(n)
One pass to build max_left, one for max_right, one to compute water. O(3n) = O(n).
6 Two pointers can solve this in O(1) space because:
Answer: At each step, we know enough about one side to compute water
If max_left < max_right, we know the left side is the bottleneck. We can safely compute water at the left pointer without knowing the exact max_right (just that it's >= max_left).

Solution

def trap(height: List[int]) -> int:
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    
    return water

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Two Pointers problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye