Trapping Rain Water

Given an int[] of n non-negative integers representing an elevation map where every bar has width 1, compute how much water it can trap after raining.

LeetCode: 42. Trapping Rain Water

Example

Text

Input:  [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

       #
   #~~~##~#
 #~##~######
012345678901   (index mod 10; ~ is water)

The water above bar i is limited by the tallest bar on its left and the tallest on its right:

Text

water[i] = min(max(height[0..i]), max(height[i..n-1])) - height[i]

Brute force: look both ways from every bar

Java

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

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

Output

6
9

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

Both ranges include i, so Math.min(leftMax, rightMax) >= height[i] and each term is never negative.

A monotonic stack: fill layer by layer

Keep a stack of bar indices with decreasing heights: bars that could be the left wall of a pool. When a taller bar i arrives, it's the right wall for every shorter bar on the stack. Pop such a bar (bottom). The bar now on top of the stack is the left wall, and the water above bottom between the two walls forms one horizontal layer:

Text

width  = i - left - 1
height = min(height[left], height[i]) - height[bottom]

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>(); // indices, heights decreasing
        int total = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int bottom = stack.pop();
                if (stack.isEmpty()) {
                    break; // no left wall, the water would run off
                }
                int left = stack.peek();
                int depth = Math.min(height[left], height[i]) - height[bottom];
                total += depth * (i - left - 1);
            }
            stack.push(i);
        }
        return total;
    }

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

Output

6
9

Time: O(n): each index is pushed and popped once. Space: O(n).

Optimal: two pointers

Precomputing both maximums for every bar takes O(n) space. Two pointers avoid it. Move left and right towards each other, tracking leftMax and rightMax so far. If height[left] < height[right], the right side already has a bar taller than height[left], so the water at left is limited by leftMax alone, whatever lies between. Settle left and move it. Otherwise settle right the same way.

Java

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

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

Output

6
9
6 0

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

The tallest bar is never settled by either pointer before the other pointer reaches it, and that bar can't hold water above itself, so stopping at left == right loses nothing.

Edge cases

Fewer than three bars: no water.
Monotonic heights: no water, because one side has no taller wall.
Large maps: the total can exceed Integer.MAX_VALUE for long, tall maps, and int arithmetic then wraps silently. Use a long total if the constraints need it.