Trapping rain water

Each bar traps water up to the shorter of the tallest wall on its left and its right, tracked with two pointers.

The idea

The water above a bar is bounded by the shorter of the tallest wall to its left and to its right. Whichever side currently has the lower wall has a known, final cap, so resolve that side and move inward; the taller side can only matter later.

Code

public static int Trap(int[] h) {
    int l = 0, r = h.Length - 1, leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            leftMax = Math.Max(leftMax, h[l]);
            water += leftMax - h[l];
            l++;
        } else {
            rightMax = Math.Max(rightMax, h[r]);
            water += rightMax - h[r];
            r--;
        }
    }
    return water;
}

Tips

• leftMax and rightMax only ever grow, so the running totals never need recomputing from scratch.
• The side with the shorter current wall is always safe to resolve: a taller wall could still appear on the other side, but never on this one.

In the .NET library

A simpler O(n)-space version precomputes a leftMax array and a rightMax array first, then combines them in a second pass. This two-pointer version does the same job in O(1) space.