LeetCode 42. Trapping Rain Water

Question

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

Source: https://leetcode.com/problems/trapping-rain-water/

Solution

The main idea is to calculate and sum up the volume of water trapped on each bar. For bar i, the volume of water on it is determined by the max heights on its left and right sides. $v = min(leftMax, rightMax) - height[i]$.

Thus, the most naive solution is to cache the leftMax and rightMax for each bar. Then we traverse height again and calculate the volume of trapped water. The thought of caching is similar to DP but this solution does not have a classic transition phase.

A more space-efficient solution is two-pointer. The key point is that we do not have to get both accurate left max and right max, but get the min of them. We maintain two variables leftMax, rightMax, which store the max values on the left of left pointer and the right of right pointer respectively. For left, leftMax is trusted but rightMax may be less than the real right max value for left. For right, the situation is similar to left.

// Cache left max and right max
// Time Complexity O(n)
// Space Complexity O(n)
public int trap(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int len = height.length;
    int[] leftMax = new int[len]; // leftMax[i] is the max value in height[:, i]
    int[] rightMax = new int[len]; // rightMax[i] is the max value in height[i, :]
    // init
    int max = 0;
    for (int i = 0; i < len; i++) {
        max = Math.max(max, height[i]);
        leftMax[i] = max;
    }
    max = 0;
    for (int i = len - 1; i >= 0; i--) {
        max = Math.max(max, height[i]);
        rightMax[i] = max;
    }
    int volume = 0;
    for (int i = 0; i < len; i++) {
        // the volume of trapped rain on index i depends on its left max height and right max height
        volume += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return volume;
}

// Two-pointer
// Time Complexity O(n)
// Space Complexity O(1)
public int trap2(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int len = height.length;
    int left = 0, right = len - 1;
    int leftMax = 0; // the max value in height[:, left]
    int rightMax = 0; // the max value in height[right, :]
    int volume = 0;
    // no need to consider left == right,
    // because for left == right == i, leftMax == rightMax == height[i],
    // the volume of water trapped on this bar is zero
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) {
            // trusty case for height[left]
            volume += leftMax - height[left];
            left++;
        } else {
            // trusty case for height[right]
            volume += rightMax - height[right];
            right--;
        }
    }
    return volume;
}