Trapping Rain Water

Problem Description

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

Constraints

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

Two Pointers and Boundary Tracking

For any index i, the volume of water trapped is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the height of the bar itself: water[i] = min(left_max, right_max) - height[i]. Instead of computing left and right maximums using O(n) memory arrays, we can use two pointers left and right initialized at the ends. Track left_max and right_max. If left_max < right_max, we can determine the water level at the left pointer since the restricting boundary is left_max. We add left_max - height[left] to our total, and increment left. Otherwise, the right boundary is the restricting factor. We add right_max - height[right] to our total, and decrement right.

Solution 1: Left-Right Boundary Two-Pointer Scan

Inward scan using two pointers to balance elevation peaks with O(1) space.

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int trappedWater = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trappedWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trappedWater += rightMax - height[right];
                }
                right--;
            }
        }
        return trappedWater;
    }
}

class Solution:
    def trap(self, height: list[int]) -> int:
        if not height:
            return 0
            
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        trapped_water = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    trapped_water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    trapped_water += right_max - height[right]
                right -= 1
                
        return trapped_water

#include <vector>
#include <algorithm>

class Solution {
public:
    int trap(std::vector<int>& height) {
        if (height.empty()) return 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int trappedWater = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trappedWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trappedWater += rightMax - height[right];
                }
                right--;
            }
        }
        return trappedWater;
    }
};

Complexity Analysis

• Time Complexity: O(n) since the two pointers meet in the middle, visiting each element exactly once.
• Space Complexity: O(1) auxiliary space as we track boundaries using simple variables.

Where It Breaks

If the inputs represent dynamic heights that change over time, precomputing or running the full scan for every query becomes too expensive. Under those conditions, a segment tree is required.

Common Mistakes

• Incorrect pointer update criteria: Comparing left_max and right_max instead of height[left] and height[right] to decide which pointer to advance.
• Negative water volume: Forgetting to check if the current bar’s height is less than the boundary maximum before adding to the sum, which can result in subtracting water.

Frequently Asked Questions

Why is it safe to advance the left pointer when height[left] < height[right]? Since height[left] < height[right], we are guaranteed that whatever left_max is, it is less than or equal to the peak on the right side. Therefore, the water level at the left pointer is bounded by left_max, not by anything to its right.

Can this be solved using a stack? Yes, using a monotonic decreasing stack to store index values can compute trapped water by horizontal layers. It has the same O(n) time complexity but uses O(n) auxiliary space.

← All Problems