Trapping Rain Water

NeetCode: Trapping Rain Water · LeetCode: 42. Trapping Rain Water · Difficulty: Hard

Given n non-negative integers representing bar heights (each of width 1), compute how much water is trapped after raining.

Example

Text

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

Brute force: for each bar, look left and right

Water above bar i rises to min(tallest bar to the left, tallest bar to the right), minus the bar's own height. Sum that over all bars, recomputing both maxima each time.

Java

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;
            for (int j = 0; j <= i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int j = i; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }
            total += Math.min(leftMax, rightMax) - height[i];
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.trap(new int[]{0, 2, 0, 3, 1, 0, 1, 3, 2, 1}));
        System.out.println(s.trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}

Output

9
9

Time: O(n²). Space: O(1).

Better: precompute prefix and suffix maxima

Two arrays, left_max[i] and right_max[i], can be filled in one pass each, which makes the per-bar lookup O(1).

Java

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        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 total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.trap(new int[]{0, 2, 0, 3, 1, 0, 1, 3, 2, 1}));
        System.out.println(s.trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}

Output

9
9

Time: O(n). Space: O(n).

Optimal: two pointers with running maxima

Only the smaller of the two side maxima matters. If left_max < right_max, the water above left is decided by left_max alone, because a taller wall is guaranteed to exist on the right. Settle that bar and move left; otherwise settle right. The two arrays collapse into two variables.

Java

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int left = 0, right = height.length - 1;
        int leftMax = height[left], rightMax = height[right];
        int total = 0;
        while (left < right) {
            if (leftMax < rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]);
                total += leftMax - height[left];
            } else {
                right--;
                rightMax = Math.max(rightMax, height[right]);
                total += rightMax - height[right];
            }
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.trap(new int[]{0, 2, 0, 3, 1, 0, 1, 3, 2, 1}));
        System.out.println(s.trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}

Output

9
9

Time: O(n). Space: O(1).

The total is an int, which wraps silently on overflow; use long if the bars can be tall and numerous. The examples here are small.