Trapping Rain Water, from brute force to two pointers

The water that sits on top of any single bar is capped by the shorter of the two tallest walls to its left and right. That one sentence is the whole problem. Once it clicks, the only thing left to decide is how much work you do to find those two walls for every position, and that is exactly what an interviewer is grading when they hand you this one.

The setup: you get an array of non-negative integers where each value is the height of a bar one unit wide. Rain falls on the skyline they form, and water pools in the dips between taller bars. Return the total units trapped. LeetCode files it as problem 42 and marks it Hard, mostly because the slow approach is easy to reach for and the fast one needs an idea you either see or you don’t. It shows up in big-tech onsite loops and at trading firms that like array manipulation under time pressure. The standard example, [0,1,0,2,1,0,1,3,2,1,2,1], traps 6 units.

Read one position to see the rule in action. Take the bar at index 5, height 0. The tallest bar to its left is the 2 at index 3; the tallest to its right is the 3 at index 7. Water rises only to the shorter wall, height 2, so this slot holds 2 - 0 = 2 units. Do that for every index, sum the dips, and you land on 6. Every solution below computes the same per-position quantity. They differ only in how cheaply they find those two walls.

The brute force everyone writes first

Walk every index. For each one, scan left for the tallest bar from the start up to here, scan right for the tallest from here to the end, and the water resting on the current bar is min(left_max, right_max) - height[i]. Because both maxes include the current bar, that value never goes negative, so you can add it straight to the total.

def trap(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 correct, and on a twelve-bar input it returns instantly. The trouble is the two scans hiding inside the loop. Every index re-walks the array to rebuild walls it computed moments ago, which puts you at O(n²) time. LeetCode’s larger cases run to tens of thousands of bars, and this version times out on them. Say that out loud as you write it, because the interviewer is waiting to hear you notice the repeated work.

Compute each wall once

The fix is to stop recomputing. The tallest bar to the left of position i only ever grows as i moves right, so a single forward pass can record left_max[i] for every index. One backward pass does the same for right_max[i]. A third pass sums the water with the same formula you already used.

def trap(height):
    if not height:
        return 0
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    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])
    total = 0
    for i in range(n):
        total += min(left_max[i], right_max[i]) - height[i]
    return total

Three linear passes give O(n) time, and the two arrays cost O(n) space. This is where most candidates land under pressure, and it is a good place to land. If you stop here you have a clean linear solution and a clear story about why it beats the first attempt. Plenty of strong engineers would ship exactly this and move on.

Two pointers and why you move the shorter side

You can throw the arrays away. The observation: at any moment you only need the binding wall, and the binding wall is whichever side is currently shorter. Put a pointer at each end and track the tallest bar seen so far from the left and from the right. Compare the two bars under the pointers. Whichever bar is shorter, that side’s running max is the wall that fixes how much water sits there, so bank it and step that pointer inward.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 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

The part that trips people up is that you branch on the current bars, height[left] versus height[right], not on the two maxes. It still holds. When height[left] is the shorter of the pair, there is a bar on the right at least as tall standing guard, so the water at the left position cannot be limited by anything further right. It is limited by the tallest bar you have already walked past on the left, which is exactly left_max. You commit that water and advance, never needing to know what the rest of the right side looks like. The logic runs mirror-image when the right bar is the shorter one.

One scan, two integers of extra state: O(n) time and O(1) space. This is the version worth drilling until you can write it without thinking, because it shows you grasped the structure instead of memorizing a pass count.

A few ways it breaks in practice. Updating the running max after you add water instead of before means you subtract from a stale wall and undercount. Branching on left_max versus right_max in one place and on the raw bars in another quietly corrupts the total, so pick one form and stay with it. And an empty array should return 0 rather than indexing into nothing, which the guard at the top of the array version handles and the two-pointer loop sidesteps because left < right is false from the start.

Which one to actually write

Approach	Time	Space	Where it lands
Brute force, rescan each side	O(n²)	O(1)	times out on large inputs; useful only as the thing you improve on
Prefix and suffix max arrays	O(n)	O(n)	the safe, fully acceptable answer
Two pointers	O(n)	O(1)	what earns the nod; the one to rehearse

A sane way to run the live round: state the brute force, write it if they want to see baseline code, then call out the repeated scans and offer the array version. If there is time, or if they ask for better than O(n) space, build the two-pointer solution and walk the shorter-side argument slowly. Showing the climb from naive to optimal usually buys you more than jumping straight to the fast answer, because they cannot tell whether you memorized the climb.

The follow-ups interviewers reach for

The one-dimensional version rarely ends the conversation. Common extensions:

• Trapping Rain Water II, the 2D grid where water escapes through the lowest point on the boundary. A min-heap over the border cells, expanding inward toward the interior, is the standard tool, and it is a real jump in difficulty.
• Returning the water level at each position rather than the sum, which is just the min(left_max, right_max) value you are already computing.
• Bars arriving as a stream, where you cannot see the whole array up front and the two-pointer trick stops applying cleanly.

If your interviewer leans toward data-structure depth, they may push you toward a monotonic stack instead. It also runs in O(n), settling water in horizontal layers as it pops bars off a decreasing stack. It is harder to derive on the spot and easier to fumble than two pointers, so reach for it only when asked or when the discussion is already drifting toward stack problems. For the plain elevation map, the two-pointer scan is the cleanest thing you can put on the whiteboard, and being able to defend why you move the shorter side is what proves you understood the reason it works.