Trapping Rain Water

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 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Approach: Two Pointers (Optimal O(1) Space)

Algorithm

1. Place two pointers, one at each end, and track the maximum height seen on each side
2. At each step, process the side with the smaller max height (the bottleneck)
3. The water trapped at a position equals its limiting max height minus its own height
4. Move the pointer inward and repeat

Time & Space Complexity

• Time Complexity: O(n) - single pass with two pointers
• Space Complexity: O(1) - only constant extra space

Java Implementation

public class TrappingRainWater {

    /**
     * Compute the total water trapped after raining.
     * @param height Elevation map heights
     * @return Total trapped water
     */
    public static int trap(int[] height) {
        int lo = 0;
        int hi = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;

        while (lo <= hi) {
            if (leftMax <= rightMax) {
                // Left side is the bottleneck
                if (height[lo] >= leftMax) {
                    leftMax = height[lo];
                } else {
                    water += leftMax - height[lo];
                }
                lo++;
            } else {
                // Right side is the bottleneck
                if (height[hi] >= rightMax) {
                    rightMax = height[hi];
                } else {
                    water += rightMax - height[hi];
                }
                hi--;
            }
        }

        return water;
    }

    // Test method
    public static void main(String[] args) {
        int[] height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]");
        System.out.println("Output: " + trap(height1)); // Expected: 6

        int[] height2 = {4, 2, 0, 3, 2, 5};
        System.out.println("Input: height = [4,2,0,3,2,5]");
        System.out.println("Output: " + trap(height2)); // Expected: 9
    }
}

Alternative Approach: Precompute Left/Right Max (O(n) Space)

Compute leftMax[i] (the tallest bar to the left of or at i) and rightMax[i] (the tallest bar to the right of or at i). Water at index i is min(leftMax[i], rightMax[i]) - height[i].

public class TrappingRainWaterPrefixed {

    public static int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return water;
    }
}

Example Walkthrough

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

The limiting heights are [0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 0, 0]. Summing these values gives 6 units of trapped water.

Key Points

1. Bottleneck Principle: Water at any position is capped by the smaller of the tallest bars on either side
2. Two Pointers: Process the side with the smaller max height to guarantee correctness in one pass
3. O(1) Space: The two-pointer version uses no auxiliary arrays
4. Alternative: Precomputing left/right max arrays is simpler to reason about but uses O(n) space
5. Edge Cases: Heights that are monotonic (always rising/falling) trap no water