42. Trapping Rain Water Hard

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

Approach

Input: An integer array height.

Output: Calculate how much rainwater can be trapped after raining.

This is an opposite-direction two pointers problem.

• We can think of each step as a wooden bucket with different left and right heights.
• The height of the left side of the bucket is the prefix maximum.
• The height of the right side of the bucket is the suffix maximum.
• Water the bucket can trap = min(left side height, right side height) - the height of the bottom of the bucket (bar height).

So, we can first calculate the prefix maximum height left_max for each bucket, and the suffix maximum height right_max for each bucket.

Then, iterate through each bucket. min(left_max[i], right_max[i]) - height[i] is the amount of water each bucket can trap.

Space Optimization Strategy

We can use an array to store the maximum heights on the left and right sides of each bucket, but we can also use two pointers to solve this.

Suppose when we iterate to a bucket, we can know either the left side height or the right side height.

• If we know the left side height of the current bucket is left_max.
• Even if we don't know the right side height of the current bucket, we know the maximum height of the bucket pointed to by the right pointer right_max.
• When left_max < right_max, the water the current bucket can hold is left_max - height[i].
• Because even if the immediate right side height of the current bucket is 0, there is a taller bucket further to the right, so it can still hold this much water.
• The same logic applies to the right side. This way, we can optimize the space complexity to O(1).

Implementation

python

class Solution:
    def trap(self, height: List[int]) -> int:
        # Treat each column as a water bucket. The left end is the left max, the right end is the right max. 
        # Trapped water = shorter side of the bucket - bucket bottom height (step height)
        n = len(height)
        if n == 0:
            return 0  # Edge case handling

        # left_max[i] represents the height of the tallest bar to the left of position i (including i)
        left_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(height[i], left_max[i - 1])

        # right_max[i] represents the height of the tallest bar to the right of position i (including i)
        right_max = [0] * n
        right_max[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])

        # Iterate through each position to calculate how much water current position can hold
        total_water = 0
        for i in range(n):
            # Water level at current column = min(highest on left, highest on right) - current height
            water_level = min(left_max[i], right_max[i])
            trapped = water_level - height[i]
            total_water += trapped

        return total_water

javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const n = height.length;
    const leftMax = Array(height.length).fill(0);
    const rightMax = Array(height.length).fill(0);

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

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

    let ans = 0;
    for (let k = 0; k < n; k++) {
        ans += Math.min(leftMax[k], rightMax[k]) - height[k]
    }

    return ans;
};

Space-Optimized Version

python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        
        # Initialize left and right pointers and corresponding maximum heights
        left, right = 0, n - 1
        left_max, right_max = 0, 0
        total_water = 0  # Accumulated trapped rainwater

        # Traverse while the left and right pointers have not met
        while left <= right:
            # Maintain the current maximum heights on the left and right sides
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            # Process whichever maximum height is smaller first
            if left_max < right_max:
                # Left side is the bottleneck. Trapped water = left max height - current height
                total_water += left_max - height[left]
                left += 1
            else:
                # Right side is the bottleneck. Trapped water = right max height - current height
                total_water += right_max - height[right]
                right -= 1

        return total_water

javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let leftMax = 0;
    let rightMax = 0;
    let left = 0;
    let right = height.length - 1;

    let ans = 0;
    while (left <= right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        if (leftMax < rightMax) {
            ans += leftMax - height[left];
            left++;
        } else {
            ans += rightMax - height[right];
            right--;
        }
    }

    return ans;
}

Complexity Analysis

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

Links

42. Trapping Rain Water (English)42. 接雨水 (Chinese)