Coding Interview: How Do You Solve Trapping Rain Water with Two Pointers?

Problem and Applicable Scenarios

Given a nonnegative integer array height of length n, height[i] is the height of the bar at index i, and every bar has width 1. Compute the total rain water trapped by these bars. For example:

height = [4, 2, 0, 3, 2, 5]
result = 9

The target is O(n) time and O(1) auxiliary space. The standard constraints are 1 <= n <= 20000 and 0 <= height[i] <= 100000. Heights are never negative, and the main problem does not ask for the water stored above every individual bar.

There is direct public interview evidence for the question. A June 2025 report from a Baidu Go backend internship interview lists Trapping Rain Water as one of three live coding tasks. A separate public phone-screen report adds a variant in which a finite amount of water is poured at a chosen position. The English and Chinese LeetCode problem pages classify it as hard and tag it with arrays, two pointers, dynamic programming, stacks, and monotonic stacks. The core skill is deriving and proving a linear algorithm from a local formula, so the category is coding regardless of the implementation language or job family.

What the Interviewer Is Evaluating

First, can you state the correct amount above one bar? The water level at index i is limited by the shorter of the highest bar on its left and the highest bar on its right, not by the two neighboring bars. If leftMax[i] and rightMax[i] both include index i, the amount is min(leftMax[i], rightMax[i]) - height[i].

Second, can you compress the prefix and suffix arrays into constant space? Storing every left and right maximum gives an easy O(n)-time solution. Two pointers use the stronger observation that the smaller known boundary is already enough to finalize one side, one column at a time.

Third, do you actually understand the movement rule? Repeating “move the shorter pointer” is not a proof. A strong answer states loop invariants and handles both cases: the current bar either raises its side's boundary or remains below it. That argument must show why the unscanned region cannot change the amount just finalized.

Finally, can you compare alternatives accurately? Prefix and suffix arrays are easiest to explain. A monotonic stack settles horizontal basins and transfers naturally to related stack problems. Two pointers use the least space. All three can be correct, but they have different space bounds, proof styles, and extensions.

Clarifying Questions Before Answering

• Does every bar have width 1? Yes. With varying widths, multiply each column's water depth by its width.
• Are heights guaranteed to be nonnegative? Yes. Negative heights have no defined physical meaning here and must not silently become deeper pits.
• Can the array be empty? The standard constraints say no. This implementation naturally returns 0 for an empty array, but an API contract should still say so explicitly.
• Do we return the total or the amount at each index? The main problem returns only the total. Per-index output necessarily occupies O(n) space.
• Is constant auxiliary space required? Yes. Otherwise, prefix and suffix arrays are an easier linear solution to communicate.
• Can the numeric type overflow? Calculate the upper bound from the real constraints. Wider constraints or a narrow integer type require a wider accumulator.
• Is the input a one-dimensional profile or a two-dimensional grid? It is one-dimensional. Trapping water in a grid requires an outside-in boundary expansion.
• May the implementation mutate the input? It does not need to; the sample only reads height.

30-Second Answer Framework

“The water above one bar is the smaller of the highest bars on its two sides minus the bar's height. Prefix and suffix arrays calculate all of those maxima in linear time but use O(n) space. I can compress that state into left and right pointers plus leftMax and rightMax, which are the highest bars already scanned from each side. When leftMax <= rightMax, the known right boundary is already at least as high as leftMax. If the current left bar does not raise leftMax, its amount is fixed at leftMax - height[left]; if it raises the boundary, its amount is zero. I then advance the left pointer. The other side is symmetric. Every index is finalized once, so time is O(n) and auxiliary space is O(1).”

Step-by-Step Deep Dive

Step 1: Define the answer for one column.

Let:

L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]

Both L[i] and R[i] include height[i], so neither can be lower than the current bar and the formula needs no extra clamp to zero. The total is the sum of all water[i]. The formula also shows why checking adjacent bars fails: a distant higher boundary can set the surface for an entire basin.

Step 2: Establish a correct baseline.

| Approach | Time | Auxiliary space | Main property | |---|---:|---:|---| | Scan both sides for every index | O(n^2) | O(1) | Direct formula, repeated work | | Prefix and suffix maximum arrays | O(n) | O(n) | Easiest to implement and prove | | Monotonic decreasing stack | O(n) | O(n) | Settles basin width and depth horizontally | | Two pointers | O(n) | O(1) | Finalizes one column from one side per step |

The prefix solution builds L from left to right and R from right to left, then applies the formula. Two pointers do not redefine the water amount. They use sufficient known boundaries to finalize a column before storing every value of L and R.

Step 3: State the loop invariants.

At the start of every iteration:

1. Every index strictly left of left has been finalized according to the per-column formula.
2. Every index strictly right of right has been finalized correctly.
3. leftMax is the maximum of the scanned range height[0..left-1], with an empty maximum of 0.
4. rightMax is the maximum of height[right+1..n-1], again using 0 for an empty range.
5. water is the sum for all finalized indices.

The unprocessed interval is always [left, right]. Each iteration must prove that at least one end can be finalized permanently before shrinking this interval.

Step 4: Prove why the side with the smaller known boundary may move.

Suppose leftMax <= rightMax and consider height[left]:

• If the current bar is higher than leftMax, it becomes the new highest left boundary. The bar is

its own left boundary, so its trapped amount is 0.

• If the current bar is no higher than leftMax, the true maximum to its right is at least the

already observed rightMax, and rightMax >= leftMax. The smaller boundary is therefore fixed at leftMax, making the amount exactly leftMax - height[left].

Neither case needs the exact shape of the unscanned middle, so the left column can be finalized. If leftMax > rightMax, the proof is symmetric for the right column. This is a comparison of known maximum boundaries, not a guess based on neighboring bars.

Step 5: Implement the two-pointer algorithm.

def trap(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    left_max = 0
    right_max = 0
    water = 0

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

    return water

The condition is left <= right, so the last column is finalized when the pointers meet. Updating the boundary before adding the difference makes a new maximum contribute zero and keeps every increment nonnegative. For an empty array, right starts at -1, the loop does not run, and the function returns 0.

Step 6: Trace [4, 2, 0, 3, 2, 5].

index  height  side   boundary after update  added water  total
0      4       left   leftMax=4              0            0
5      5       right  rightMax=5             0            0
1      2       left   leftMax=4              2            2
2      0       left   leftMax=4              4            6
3      3       left   leftMax=4              1            7
4      2       left   leftMax=4              2            9

The bar of height 5 supplies a known right boundary high enough for every remaining left column, so the algorithm keeps finalizing the left side. Every column appears exactly once, with no basin counted twice.

Step 7: Prove termination, correctness, and complexity.

Initially, both processed ranges are empty, so the invariants hold. Step 4 proves that the column added in each iteration receives exactly its per-column amount. Updating leftMax or rightMax preserves its definition for the next iteration. Every iteration either increments left or decrements right; after finitely many steps, left > right. At that point every index has been finalized correctly, so the sum is correct.

Each index is visited once, giving O(n) time. The algorithm allocates no input-sized storage beyond the output-free scalar result; two pointers, two boundaries, and one accumulator use O(1) auxiliary space.

Step 8: Verify against a formula oracle and adversarial cases.

Fixed tests should include one bar, two bars, all zeros, strictly increasing and decreasing inputs, all equal heights, several separate basins, a flat-bottomed basin, the standard examples, and [3, 0, 3]. The last case exposes an implementation that incorrectly uses left < right and skips the meeting index.

For short random nonnegative arrays, build L and R, use the per-column formula as an oracle, and compare it with the two-pointer result. Also check that the result is nonnegative, reversing the array preserves the total, and adding a zero-height bar at either outer end does not change the original total. Differential tests find implementation errors; the invariant proof remains the correctness argument.

Strong Sample Answer

“I first reduce the problem to a per-index formula. The depth at i is min(max(height[0..i]), max(height[i..n-1])) - height[i]. Two prefix arrays implement that formula in O(n) time and O(n) space. To meet constant auxiliary space, I use two pointers.

Inside the loop, leftMax and rightMax are the highest bars already scanned outside the two pointers. If leftMax <= rightMax, I finalize the left pointer. If its current bar raises leftMax, its amount is zero. Otherwise, the known rightMax is already at least as high as the left boundary, so the unknown middle cannot reduce the smaller boundary below leftMax; the amount is fixed at leftMax - height[left]. I then move left inward. The right side is symmetric.

Each iteration permanently handles one column, so all columns are done at termination. Time is O(n), and the pointers, boundaries, and accumulator use O(1) auxiliary space. I would test short inputs, monotone and equal arrays, multiple basins, and [3, 0, 3], then differentially compare short random cases with the prefix-array formula.”

Common Mistakes

• Subtracting from the larger of the two maxima → Water spills over the shorter boundary → Always use the smaller maximum.
• Checking only adjacent bars → A distant boundary is ignored → Start from the full left/right per-column formula.
• Adding before updating the current boundary → A new maximum can produce a negative amount → Update first, then add a nonnegative difference.
• Using left < right → The middle of [3, 0, 3] can remain unprocessed → Include the meeting position in the loop.
• Moving the larger-boundary side without a proof → The unknown opposite side may still set the lower surface → Finalize only the side backed by a known opposite boundary.
• Applying the Container With Most Water formula → width × boundary height double-counts bars and columns → Sum the water depth above each bar.
• Stopping the analysis at constant work per iteration → It does not explain why future bars cannot change the answer → State the boundary invariants and the two-case proof.
• Claiming a monotonic stack also uses O(1) space → A monotone input can retain n indices → Report O(n) worst-case space.
• Testing only the illustrated example → Meeting, monotone, and equal-height boundaries remain unchecked → Add fixed cases and a prefix-array oracle.

Follow-Up Questions and Responses

Follow-up 1: Why not compare height[left] and height[right] directly?

Another correct formulation compares the current endpoint heights, but it needs a matching invariant and update order. This implementation compares leftMax and rightMax because those values map directly to the per-column boundary formula. Do not combine one formulation's condition with the other formulation's proof; choose one and keep the code, explanation, and proof consistent.

Follow-up 2: What if the function must return the water above every bar?

Write each finalized increment into an array of length n, then sum it or accumulate the total at the same time. Runtime remains O(n), while the output itself requires O(n) space. If a caller consumes results as a stream, note that two pointers do not finalize indices in left-to-right order; include the index or reorder the completed output.

Follow-up 3: What if heights arrive only as a left-to-right stream?

An exact answer depends on a future right boundary, so every column cannot be finalized immediately with fixed memory. A monotonic stack can retain open basins and settle them when a high enough right boundary arrives, but its worst-case memory is still O(n). A hard memory bound requires an approximation, external storage, or a second pass; it cannot preserve the original exact constant- space promise.

Follow-up 4: What if bars have different widths?

If bar i independently spans width[i], the boundary-height logic stays the same and its volume is waterDepth[i] * width[i]. If the input instead gives irregular coordinates and gaps, first define the height over every horizontal interval. The distance between neighboring bar centers is not automatically the width of an entire bar.

Follow-up 5: How do you trap water on a two-dimensional height map?

A grid cell is constrained by the whole outer boundary, so two directional pointers are insufficient. A common algorithm inserts all boundary cells into a min-heap and repeatedly expands inward from the lowest current boundary. A lower unvisited neighbor contributes the height difference, and the higher of the boundary and neighbor becomes the effective boundary for later expansion. With a visited set, an m × n grid takes O(mn log(mn)) time and O(mn) space.

Follow-up 6: When is the monotonic-stack solution preferable?

The stack is natural when a follow-up asks for each basin closed by left and right boundaries, for a horizontal width explanation, or for a transition to histogram-style monotonic-stack problems. It stores indices in decreasing-height order. A higher bar pops a basin bottom; the new stack top and current bar form its boundaries, and the algorithm adds effective width × new water-layer depth. Total time is still O(n), with O(n) worst-case auxiliary space.