Trapping Rain Water

Problem Overview

Given an array representing an elevation map, compute how much water it can trap after raining, using each bar's width as 1 unit.

Why solve this?

The capstone Two Pointers problem in this course: it looks like it needs two full prefix/suffix arrays, but a running leftMax/rightMax invariant lets converging pointers compute the same answer in a single pass with O(1) space.

Pattern Recognition

Whenever the amount trapped or bounded at a position depends on the minimum of the best value seen so far from each side, and computing both sides with separate prefix/suffix arrays feels wasteful, check whether tracking just the smaller running boundary as you converge is enough.

Prerequisites

• Container With Most Water — the same converging-pointer shape, applied to a running-maximum invariant instead of a single width times height product.

Hints

1. The water trapped above any single bar is limited by the shorter of the tallest bar to its left and the tallest bar to its right.
2. You don't need to precompute both a full left-max array and a full right-max array — a two-pointer sweep can track just enough of each side as it goes.
3. At each step, process whichever side currently has the smaller running maximum — that side's water level is already fully determined, regardless of what the far side's tallest bar turns out to be.

Approach

Use two pointers, left starting at index 0 and right at the last index, along with two running values leftMax and rightMax tracking the tallest bar seen so far from each side. At each step, compare height[left] and height[right]: process whichever side is currently shorter, because that side's trapped water is fully determined — it can only ever be limited by its own side's running max, since the far side already has at least an equally tall boundary. If the current bar on that side is at least as tall as its running max, update the running max (no water trapped here, but the boundary rises). Otherwise, the difference between the running max and the current bar is exactly the water trapped above that position, so add it to the total. Move that side's pointer inward and repeat until the pointers meet. This avoids storing full left-max and right-max arrays, doing the same computation in one pass with O(1) extra space; the alternative is precomputing prefix-max and suffix-max arrays, which finds the same answer in the same time complexity but trades the O(1) space for O(n).

Code

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

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy