Trapping Rain Water — Two-Pointer in O(n)

Trapping Rain Water looks intimidating, but it collapses to one idea: each column traps min(maxLeft, maxRight) - height[i] units of water. Lock that in and the two-pointer solution writes itself.

The Problem

Given a non-negative integer array height where each element represents a unit-width bar, compute how much water it can trap after raining.

Example:

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

The water sits in valleys bounded by taller bars on both sides.

Intuition

For every index, water trapped equals min(maxLeft, maxRight) - height[i]. The brute force scans left and right at every index — O(n^2). A prefix/suffix max array brings it down to O(n) time and O(n) space.

The two-pointer trick gets O(1) space. Track left_max and right_max as you walk inward from both ends. The pointer with the smaller current bar moves; the smaller side is the bottleneck, so the water level at that pointer is fully determined no matter what is on the other side. That invariant — bottleneck side is locked — is the whole insight.

Explanation with Example

Take height = [0,1,0,2,1,0,1,3,2,1,2,1].

• Start left=0, right=11. height[left]=0 < height[right]=1, so process left. left_max becomes 0, no water added, advance.
• At left=2 (height 0), left_max=1, add 1-0=1 unit.
• At left=5 (height 0), left_max=2, add 2-0=2.
• At left=6 (height 1), add 2-1=1.
• From the right side, when right lands on heights below right_max=3, additional units accumulate.

Total trapped = 6.

height  0 1 0 2 1 0 1 3 2 1 2 1
                     #
      . . . . . . . ## . . .
      . . . # ~ ~ ~ ## # ~ #
      . # ~ ## # ~ ## ## ## #
      l ->                <- r

at i=2: min(1, 3) - 0 = 1 unit
at i=5: min(2, 3) - 0 = 2 units

Code

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    total = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                total += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                total += right_max - height[right]
            right -= 1
    return total

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]) {
                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;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = (int)height.size() - 1;
        int leftMax = 0, rightMax = 0, 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;
    }
};

Edge Cases

• Empty array or length less than 3: return 0; nothing can hold water.
• Strictly increasing or decreasing arrays: no valleys, answer is 0.
• A flat plateau like [3,3,3]: still 0.
• Single-cell valleys like [3,0,3]: traps 3 units.
• Large bars at the ends only, e.g., [5,0,0,0,5]: traps 15 units.

Complexity Analysis

• Brute force: O(n^2) time, O(1) space.
• Prefix/suffix max arrays: O(n) time, O(n) space.
• Two pointer: O(n) time, O(1) space.

The two-pointer version is the gold standard interviewers want to hear. See Big-O notation for a refresher on why constant factors matter here.

How to Explain It in an Interview

Open with the invariant: water at index i equals min(maxLeft[i], maxRight[i]) - height[i]. Mention the O(n) prefix array solution first to show you understand the principle. Then optimize: if height[left] < height[right], the left side is the bottleneck no matter what is between them, so left_max - height[left] is final. Move the smaller pointer inward and repeat. Emphasize the invariant clearly; interviewers care more about the reasoning than the code.

Related Problems

• Container With Most Water (another classic two-pointer drill)
• Largest Rectangle in Histogram (monotonic stack)
• Trapping Rain Water II (2D version, uses a heap)
• Product of Array Except Self (similar prefix/suffix idea)

Wrap up

This problem rewards recognizing one invariant and then squeezing it into O(1) space. Once you internalize the min(leftMax, rightMax) formula, the two-pointer move is mechanical.