Trapping Rain Water

Given n non-negative integers that describe an elevation map, where each bar has width 1, compute how much water is trapped after it rains. This is LeetCode 42.

Example 1
Elevation map for heights 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 with 6 units of trapped water Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Example 2
Input: height = [4, 2, 0, 3, 2, 5]
Output: 9

How to Think About It

Step 1: Water above one bar

Look at a single bar i. Water above it is held in by the tallest bar on its left and the tallest bar on its right, and it rises to the lower of the two:

water[i] = min(maxLeft[i], maxRight[i]) - height[i]

Here maxLeft[i] and maxRight[i] include bar i itself, so the result is never negative. The answer is the sum over all bars.

Step 2: A version with extra arrays

One pass from the left fills maxLeft, one pass from the right fills maxRight, and a third pass adds up the formula. That is O(n) time and O(n) space. Two pointers remove the arrays.

Step 3: Only the smaller side matters

Keep left and right pointers, with leftMax as the tallest bar seen from the left and rightMax from the right. Suppose height[left] < height[right]:

  • There is a bar on the right of left, namely height[right], that is taller than height[left].
  • So whatever the true maxRight[left] is, the water at left is limited by the left side only: it is leftMax - height[left].

Add that, and move left right. When the right bar is the smaller one, do the mirror image on the right.

Step 4: Finish when the pointers meet

Each bar is settled exactly once, by whichever pointer reaches it.

Walkthrough

height = [4, 2, 0, 3, 2, 5]. The right end, 5, is taller than everything else, so the left pointer settles every bar.

Bar settledHeightleftMaxWater addedTotal
04400
12422
20446
33417
42429

The pointers meet at bar 5, and the total is 9.

Java Solution

The comparison between the two current bars decides which side is safe to settle.

Java
public class TrappingRainWater {

    public static int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;                      // tallest bar seen from the left so far
        int rightMax = 0;                     // tallest bar seen from the right so far
        int water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                water += leftMax - height[left];    // right side is sure to be at least as tall
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                water += rightMax - height[right];  // left side is sure to be at least as tall
                right--;
            }
        }
        return water;
    }

    public static void main(String[] args) {
        System.out.println(trap(new int[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));   // 6
        System.out.println(trap(new int[] {4, 2, 0, 3, 2, 5}));                     // 9
    }
}

The original implementation, TrappingRainWater.java, is on GitHub.

Complexity

  • Time: O(n): each bar is settled once.
  • Space: O(1), compared with O(n) for the version with two arrays.

A monotonic stack solves the same problem by filling water layer by layer: see Trapping Rain Water Using Stack. Container With Most Water is a related two-pointer problem.