LeetCode Trapping Rain Water: Two-Pointer in O(n)

Trapping Rain Water (LeetCode 42, Hard) 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.

Brute Force

For every index, scan left and right for the tallest bar, then add the trapped water at that column.

def trap_brute(height):
    n = len(height)
    total = 0
    for i in range(n):
        left_max = max(height[:i+1])
        right_max = max(height[i:])
        total += min(left_max, right_max) - height[i]
    return total

This is O(n^2) time. It is correct but will TLE on large inputs.

Optimal Solution

Use two pointers from opposite ends. Track left_max and right_max as you walk inward. The pointer with the smaller current bar moves; the smaller side is the bottleneck, so the water level at that pointer is fully determined.

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

O(n) time, O(1) extra space.

Walk Through an 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.

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’s 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

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

Wrap up

Trapping Rain Water 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. Practice writing it from scratch a few times; it shows up in interview rotations constantly and is a great signal of two-pointer fluency.