Trapping Rain water problem

The problem, simply

You get an array of non-negative numbers. Each number is the height of a bar, and every bar is 1 wide. Rain falls on all of it. Water collects in the dips between taller bars and spills off the two open ends.

Give back how many squares of water stay trapped.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each bar, look all the way left for the tallest bar there, and all the way right for the tallest bar there. The water on this bar is the shorter of those two walls minus the bar's height, if that is positive.

class Solution {
    public int trap(int[] height) {
        int n = height.length, 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]);     // tallest on the left, me included
            for (int j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]);    // tallest on the right, me included
            total += Math.min(leftMax, rightMax) - height[i];                        // never negative
        }
        return total;
    }
}

How long it takes: for each of the n bars we scan the whole row, O(n^2). Extra room: two numbers, O(1). Counting the bar itself in both maxima keeps the water from going below 0.

Way 2: the clever way

Two fingers, left and right, start at the ends. leftMax is the tallest bar the left finger has passed, rightMax the tallest the right finger has passed.

1. If height[left] < height[right], work on the left. Somewhere on the right there is a bar taller than height[left], so the water at left only depends on leftMax. If height[left] >= leftMax, it becomes the new leftMax and holds no water. Otherwise add leftMax - height[left]. Move left right.
2. Otherwise do the same on the right side with rightMax, and move right left.
3. Stop when the fingers meet.

In the side view, orange water is the water added in this step, and blue water was added earlier.

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, total = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                // the right side has a taller wall, so only leftMax matters here
                if (height[left] >= leftMax) leftMax = height[left];
                else total += leftMax - height[left];
                left++;
            } else {
                // the left side has a wall at least this tall, so only rightMax matters
                if (height[right] >= rightMax) rightMax = height[right];
                else total += rightMax - height[right];
                right--;
            }
        }
        return total;
    }
}

How long it takes: each step moves one finger, O(n). Extra room: four numbers, O(1).

Another way: two tables of walls

This is the bridge between the two ways, and many people find it easier to explain first.

1. leftMax[i] is the tallest bar from index 0 to i. Fill it walking right.
2. rightMax[i] is the tallest bar from i to the end. Fill it walking left.
3. Add min(leftMax[i], rightMax[i]) - height[i] over all bars.

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int[] leftMax = new int[n], 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;
    }
}

This is O(n) time and O(n) room. The two pointer way is the same idea with the tables replaced by two running numbers.

Watch out for

• Water on a bar is never negative. If you leave the bar itself out of the maxima, clamp with Math.max(0, ...).
• Arrays with fewer than 3 bars hold no water. The loops handle this without special code.
• For huge inputs the total can pass the int limit. Use long if heights and lengths are large.

What interviewers ask next

• Solve it with a stack. Keep indexes of bars in a stack with heights going down. When a taller bar arrives, pop the bottom of a dip, and fill the water between the new bar and the bar under it, one layer at a time. Also O(n).
• Trapping rain water in 2D (LeetCode 407). Use a min heap of the border cells and grow inward from the lowest wall, like Dijkstra.
• Container with most water (LeetCode 11). Similar two fingers, but you pick only two walls and ignore the bars in between.
• Why is the two pointer way correct? When height[left] < height[right], the right side already has a wall taller than height[left], so min(leftMax, real rightMax) is leftMax whenever it matters.

Remember this

Grown-up words: the tallest bars seen so far are prefix and suffix maximums, the two friends are two pointers, and the stack version uses a monotonic stack.