Trapping Rain Water (Two Pointer Approach)

Problem Statement

Given n non-negative heights representing an elevation map where each bar has width 1, compute how much water it can trap after raining.

Example

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Two Pointer Approach

Water above any bar is limited by the shorter of the tallest bar to its left and the tallest to its right. Use two pointers with running leftMax and rightMax. Always move the side with the smaller max inward, adding max - height as trapped water.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def trap(height):
    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

Java

int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

C++

int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

Key Takeaways

• Moving the smaller side guarantees the water bound is correct.
• Two pointers reduce the O(n) extra space of the prefix/suffix-max solution to O(1).
• A classic "hard" problem that becomes simple with the right invariant.