Trapping Rain Water: Two Pointer Approach

LeetCode's Trapping Rain Water is one of those problems that shows up in every "must-know" interview list. It is rated hard, but the optimal solution is surprisingly elegant once you see it. And the reason interviewers love it is that it has a beautiful progression: brute force to prefix arrays to two pointers, each step cutting away unnecessary work.

Let's walk through all three approaches.

The problem

You are given an array of non-negative integers representing an elevation map where the width of each bar is 1. Compute how much water it can trap after raining.

Here is the classic example:

The key insight is that water at any position depends on the tallest bars to its left and right. Water rises to the level of the shorter of those two walls, minus the height of the ground at that position. If the ground is already at or above that level, no water sits there.

For each index i, the water trapped is:

water[i] = min(max_left[i], max_right[i]) - height[i]

That single formula is the entire problem. The three approaches differ only in how efficiently you compute max_left and max_right.

Approach 1: Brute force - O(n^2) time, O(1) space

The most straightforward way. For every position, scan left to find the tallest bar, scan right to find the tallest bar, and compute the water.

def trap_brute_force(height):
    n = len(height)
    total = 0

    for i in range(n):
        left_max = 0
        right_max = 0

        # Scan left for tallest bar
        for l in range(i + 1):
            left_max = max(left_max, height[l])

        # Scan right for tallest bar
        for r in range(i, n):
            right_max = max(right_max, height[r])

        total += min(left_max, right_max) - height[i]

    return total

This works, but for each of the n positions you scan up to n elements in each direction. That is O(n^2). For large inputs, it is too slow.

Approach 2: Prefix arrays - O(n) time, O(n) space

The brute force recomputes left_max and right_max from scratch at every position. But these are just running maximums. You can precompute them in two passes.

def trap_prefix(height):
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    # Forward pass: compute max height from the left
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    # Backward pass: compute max height from the right
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    # Compute water at each position
    total = 0
    for i in range(n):
        total += min(left_max[i], right_max[i]) - height[i]

    return total

Three passes, each O(n). Time is O(n), but you need O(n) extra space for the two arrays.

This is a solid solution. Many interviewers would accept it. But there is a way to eliminate the extra space entirely.

Approach 3: Two pointers - O(n) time, O(1) space

Here is the key observation. You do not actually need both left_max and right_max to be fully computed before you start. You only need to know which side is the bottleneck.

If left_max < right_max, then the water at the left pointer is determined by left_max alone. It does not matter what right_max is, because left_max is already the smaller value. The same logic applies in reverse.

So you maintain two pointers, one on each end, along with their running maximums. At each step, process whichever side has the smaller maximum. That side's water level is fully determined.

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    total = 0

    while left < right:
        if height[left] <= height[right]:
            left_max = max(left_max, height[left])
            total += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            total += right_max - height[right]
            right -= 1

    return total

One pass. Two pointers. Two variables tracking the running maximums. That is it. O(n) time and O(1) space.

Two-pointer walkthrough

Let's trace through the algorithm on our example array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. L (orange) is the left pointer, R (green) is the right pointer.

Notice the pattern: each step processes the side with the smaller height, because that side's water level is fully determined by its own running max. The pointers converge from both ends and meet in the middle. Every index gets processed exactly once.

Why interviewers love this problem

Trapping Rain Water is a favorite for several reasons:

1. It tests visualization. You need to see the problem before you can solve it. Candidates who cannot picture water sitting between bars struggle to even write the brute force.
2. It has a clean optimization path. Brute force to prefix arrays to two pointers. Each step requires a genuine insight, not just "use a different data structure."
3. The optimal solution is short but non-obvious. The two-pointer code is about 10 lines. But explaining why it works requires understanding the invariant: the processed side always has the binding constraint.
4. It combines multiple patterns. Forward-backward passes, prefix maximums, and converging two pointers all show up. Candidates who have internalized these building blocks can piece together the solution quickly.

The building blocks

This problem is built from two fundamental bricks that appear across many LeetCode problems:

Two-pass forward-backward

The prefix array approach is an instance of the forward-backward pattern: make one pass left to right computing prefix maximums, then another right to left computing suffix maximums. This same technique shows up in:

• Product of Array Except Self (prefix and suffix products)
• Best Time to Buy and Sell Stock III (forward and backward profit passes)
• Candy (left-to-right and right-to-left neighbor comparisons)

Whenever a value depends on context from both directions, two passes are the natural solution.

Opposite-end convergence

The two-pointer solution uses the opposite-end convergence pattern: start two pointers at the extremes and move them inward based on a comparison. This is the same pattern behind:

• Container With Most Water (move the shorter side inward)
• Two Sum II (move based on sum comparison)
• Valid Palindrome (compare characters from both ends)

The invariant is always the same. Whichever pointer you move, you can prove that the other side does not need to be checked yet. You narrow the search space by one element each step, and you never backtrack.

Complexity summary

The two-pointer solution is optimal in both dimensions. You cannot do better than O(n) time because you need to look at every element at least once.

Reading about it is not enough

You have read the solution. You understand the invariant. But can you write it from scratch in three weeks when you are sitting in front of a whiteboard?

That gap between understanding and recall is where most people fail. Trapping Rain Water is the kind of problem where you nod along to the explanation, close the tab, and then blank on the pointer movement logic when it matters. The two-pass and opposite-end convergence building blocks are small enough to drill individually. Once they are in your long-term memory, assembling them into the full solution becomes straightforward.

Related posts

• The Two Pointers Pattern - The foundation of the optimal solution, with converging pointer examples
• The Sliding Window Pattern - A related technique where both pointers move in the same direction
• Best Time to Buy and Sell Stock - Another problem that uses forward-backward passes and running extremes