Trapping Rain Water

Question (LC.42)

Given an integer array representing the height of n unit width bars, find volume of rain water it can trap.

Example

I: [0,1,2]
O: 0
I: [3,1,2]
O: 1
I: [0,1,0,2,1,0,1,3,2,1,2,1]
O: 6

Analysis

The water being trapped inside any bar is determined by the highest left and right bar. The volume of water trapped = min(left, right) - height

Brute Force Three Pass

We can assign the highest left bars, assign the highest right bars, then compute the rain water.

public int trap(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int n = height.length;
    int[] leftBars = new int[n];
    int[] rightBars = new int[n];
    // assign left bars
    int left = 0;
    for (int i = 0; i < n; i++) {
        left = Math.max(left, height[i]);
        leftBars[i] = left;
    }
    // assign right bars
    int right = 0;
    for (int i = n - 1; i >= 0; i--) {
        right = Math.max(right, height[i]);
        rightBars[i] = right;
    }
    // compute the rain volume
    int rain = 0;
    for (int i = 1; i < n - 1; i++) {
        int current = Math.min(leftBars[i], rightBars[i]) - height[i];
        rain += current > 0 ? current : 0;
    }
    return rain;
}

Time O(3n) = O(n) Space O(2n) = O(n)

L/R Pointers

Linear time is probably as good as we can get. Unless we can do a binary search on the array. But the space can be further optimized.

We maintain two values leftBar and rightBar. Then use left/right pointers to update on the way.

leftBar
rightBar

left -->     <--- right

move left if leftBar is lower than rightBar
move right if rightBar is lower than the leftBar
(so we make sure water can be trapped by the lower end)

public int trap(int[] height) {
    if (height == null || height.length < 2) {
        return 0;
    }
    int rain = 0;
    int left = 0, right = height.length - 1;
    int leftBar = height[left], rightBar = height[right];
    while (left < right) {
        if (leftBar < rightBar) {
            rain += leftBar - height[left];
            left++;
            leftBar = Math.max(leftBar, height[left]);
        } else {
            rain += rightBar - height[right];
            right--;
            rightBar = Math.max(rightBar, height[right]);
        }
    }
    return rain;
}

Time O(n) Space O(1)

Follow Up (LC.407)

Trap rain water 3D version