📖 11 min read
Last updated on

Trapping Rain Water — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer draws an elevation map on the whiteboard and asks: “How much water can this trap after it rains?” You know this is a classic two-pointer problem. But now you need to derive the water formula from the geometry, walk through three progressively better solutions, and explain the two-pointer invariant precisely when the interviewer asks “why does it not matter what the right maximum is?”

This walkthrough builds the complete Trapping Rain Water explanation from first principles: the key geometric insight, every optimization step, the pointer logic explained precisely, and what the ideal interview narrative sounds like.

The Problem

Given an array height of non-negative integers representing an elevation map where each bar has width 1, compute how much water can be trapped after it rains. (LeetCode #42)

Example

Input height = [0,1,0,2,1,0,1,3,1,0,1,2]

Output 6

Visualize the height array as vertical bars. Water pools between taller bars: a low bar is covered by water up to the height of the shorter of the two tallest bars on its left and right sides. For the bar at index 5 (height 0), the tallest bar to its left is 2 and to its right is 3, so it holds min(2, 3) - 0 = 2 units of water. Summing across all positions gives 6 total units. The first and last bars never hold water because there’s nothing to contain it on their outer sides.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Trapping Rain Water rewards candidates who can derive a formula from a geometric observation rather than reaching for a memorized algorithm. Interviewers use it to test whether you can reason visually, translate that reasoning into code, and then optimize it under pressure.

SkillWhat Interviewers Observe
Geometric reasoningDo you arrive at the min(max_left, max_right) - height[i] formula independently?
Solution progressionDo you move naturally from O(n^2) to O(n) space to O(1) space?
Two-pointer intuitionCan you explain why the pointer on the shorter side can be safely advanced?
Edge case awarenessDo you handle flat arrays, monotonically increasing/decreasing arrays, and all-zero inputs?
Complexity fluencyCan you articulate time and space for each approach and justify the tradeoffs?
Verbal clarityCan you explain a non-obvious invariant (the two-pointer logic) without hand-waving?

Step 1: Clarifying Questions

Even for a well-defined problem, smart clarifying questions frame the design space and show structured thinking:

  1. Can heights be zero? Can the entire array be flat? All zeros is valid and should return 0. The formula handles it cleanly: min(0, 0) - 0 = 0.

  2. Is the array guaranteed non-empty? What about arrays of length 1 or 2? Arrays of length less than 3 can never trap water because there’s no way to form a “valley.” Worth deciding whether to add a guard clause or let the formula return 0 naturally.

  3. Are heights guaranteed to be non-negative integers? Yes, per LeetCode constraints. Negative heights would break the formula entirely.

  4. Should I return total water trapped, or water per bar? Total water, a single integer.

  5. Are there constraints on array length that hint at expected complexity? LeetCode allows up to 20,000 bars. This rules out O(n^2) brute force at scale and confirms O(n) is the target.

Step 2: A First (Non-Optimal) Idea

The most natural starting point: for each bar, scan left to find the tallest bar to its left and scan right to find the tallest to its right. The water above that bar is min(max_left, max_right) - height[i].

def trap(height):
    total_water = 0
    n = len(height)

    for i in range(n):
        max_left = max(height[:i+1])   # Tallest bar from 0 to i (inclusive)
        max_right = max(height[i:])    # Tallest bar from i to n-1 (inclusive)
        water_at_i = min(max_left, max_right) - height[i]
        total_water += water_at_i

    return total_water

This is O(n^2) in time: for each of the n bars, we scan up to n elements to find the left and right maxima. The formula is exactly right, that’s the key insight expressed directly. The inefficiency is the repeated scanning.

ApproachTimeSpace
Brute force (scan both sides per bar)O(n^2)O(1)
Prefix/suffix arraysO(n)O(n)
Two pointersO(n)O(1)

Step 3: The Key Insight

The water above bar i is min(max_left[i], max_right[i]) - height[i]. If you know one side’s max is the binding constraint, you don’t need the exact value of the other side.

There are two insights layered on top of each other:

Insight 1: The water formula. Each bar holds water equal to max(0, min(max_left, max_right) - height[i]). Water pools up to the shorter of the two surrounding peaks, and any excess above the bar itself is the water depth.

Insight 2: Precompute the maxima. Build max_left[i] (tallest bar from 0 to i) and max_right[i] (tallest from i to n-1) in two passes. Then compute water per bar in a final pass. Three O(n) passes, O(n) space.

Insight 3: Two pointers eliminate the arrays. If height[left] <= height[right], the water at left is fully determined by max_left. The right side is guaranteed to be at least as tall as the current left bar, so max_left is the binding constraint. You can safely process left and advance it inward without knowing the exact right maximum. The symmetric argument holds for right.

Bar chart of height=[0,1,0,2,1,0,1,3,2,1,2,1] with teal-shaded water regions above each trapped column, and label showing total water = 6 units. ---

Step 4: Optimal Strategy (Two Pointers)

O(n) time, O(1) space:

  1. Initialize left = 0, right = len(height) - 1.
  2. Initialize max_left = 0, max_right = 0 to track running maximums.
  3. Initialize total_water = 0.
  4. While left < right:
    • If height[left] <= height[right]:
      • If height[left] >= max_left, update max_left (new peak, no water).
      • Else, add max_left - height[left] to total_water.
      • Increment left.
    • Else:
      • If height[right] >= max_right, update max_right.
      • Else, add max_right - height[right] to total_water.
      • Decrement right.
  5. Return total_water.

The key invariant: when processing left, max_right may not reflect the true global maximum to the right. But since height[left] <= height[right], the right side is at least as tall, so max_left is the binding constraint.

Python Implementation

Approach 1: Prefix/Suffix Arrays (O(n) time, O(n) space)

def trap(height: list[int]) -> int:
    n = len(height)
    if n < 3:
        return 0

    # max_left[i] = tallest bar from index 0 to i (inclusive)
    max_left = [0] * n
    max_left[0] = height[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i - 1], height[i])

    # max_right[i] = tallest bar from index i to n-1 (inclusive)
    max_right = [0] * n
    max_right[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        max_right[i] = max(max_right[i + 1], height[i])

    # Water above each bar = min of both maxima minus bar height
    total_water = 0
    for i in range(n):
        water_at_i = min(max_left[i], max_right[i]) - height[i]
        total_water += water_at_i  # Always >= 0 since max_left/right >= height[i]

    return total_water

Approach 2: Two Pointers (O(n) time, O(1) space) — Optimal

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_left, max_right = 0, 0
    total_water = 0

    while left < right:
        if height[left] <= height[right]:
            if height[left] >= max_left:
                max_left = height[left]   # New left peak — no water here
            else:
                total_water += max_left - height[left]  # Trapped water
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]  # New right peak — no water here
            else:
                total_water += max_right - height[right]  # Trapped water
            right -= 1

    return total_water

Implementation notes worth calling out in an interview:

  • The two-pointer approach never needs a max(0, ...) clamp. Because max_left and max_right are always at least as large as the current bar height, the subtraction is always non-negative.
  • Process the pointer on the side with the smaller current height, not the smaller maximum. The comparison is height[left] <= height[right], not max_left <= max_right. This is the condition that guarantees the invariant.
  • Both pointers advance exactly once per iteration, so the while loop runs exactly n - 1 times total, confirming O(n) time.
  • Present both approaches in an interview (prefix arrays first, then two pointers) to show the optimization journey.

Time & Space Complexity

ApproachTimeSpace
Brute ForceO(n^2)O(1)
Prefix/Suffix ArraysO(n)O(n)
Two PointersO(n)O(1)

Two-pointer time: Both pointers traverse the array exactly once, each advancing one step per iteration until they meet. Every operation inside the loop is O(1). Total: O(n).

Two-pointer space: Only four scalar variables (left, right, max_left, max_right) regardless of input size. True O(1) auxiliary space.

The two-pointer solution achieves the theoretical optimum: you must examine every bar at least once (O(n) lower bound), and you need no more than constant extra storage. Stating this explicitly, “this is both time and space optimal,” is a strong closing signal.

Common Interview Mistakes

  1. Not explaining the water formula before coding. The formula min(max_left, max_right) - height[i] is the entire geometric insight. Candidates who skip straight to implementation leave the interviewer unsure whether they understand the problem or are transcribing a memorized solution.

  2. Presenting only the two-pointer solution without showing the progression. The two-pointer approach looks like magic if you haven’t first established the precomputation approach. Always walk through: brute force, prefix arrays, two pointers. The journey is the point.

  3. Misidentifying which pointer to advance. The rule: advance the pointer on the side where height[left] <= height[right]. Advancing the wrong pointer breaks the invariant and produces wrong results.

  4. Forgetting to update the running maximum before computing water. For a bar that is a local peak, you update max_left or max_right and add zero water. Forgetting the update causes future bars to compute water against a stale maximum.

  5. Confusing the two-pointer comparison. The comparison is on current bar heights (height[left] vs height[right]), not on running maxima. Using max_left <= max_right as the condition produces subtly wrong results.

  6. Not handling arrays of length less than 3. An array with fewer than 3 bars can’t trap water. While the two-pointer loop handles this correctly by terminating immediately, stating this edge case signals thoroughness.

  7. Declaring the solution correct without tracing through an example. The two-pointer invariant is non-obvious. Trace through [0,1,0,2,1,0,1,3,1,0,1,2] step by step out loud to catch bugs.

What a Strong Candidate Sounds Like

“Let me start with the key observation: the water above any bar at index i is determined by the tallest bar to its left and the tallest bar to its right. Specifically, it holds min(max_left, max_right) - height[i] units.

Brute force computes those maxima from scratch for each bar: O(n^2) time. I can improve that by precomputing prefix max and suffix max arrays in two single passes, giving O(n) time and space.

To get O(1) space, I use two pointers. The key insight: if height[left] <= height[right], the water at left is fully determined by max_left. The right side is guaranteed to be at least as tall, so it’s not the binding constraint. I can safely process left and advance it inward. The symmetric argument holds for the right pointer. Each pointer advances exactly once, giving O(n) time and O(1) space.

Let me trace through the example to verify the invariant holds, then code it up.”

Example Interview Dialogue

Interviewer: Given an elevation map as an array, compute how much water it traps after rain.

Candidate: Before I start: heights are non-negative integers, and I’m returning total water as a single integer, right?

Interviewer: Correct.

Candidate: Great. The core observation: each bar holds water equal to min(tallest_left, tallest_right) - its_own_height. Brute force recomputes tallest left and right for every bar, which is O(n^2). I can precompute prefix and suffix max arrays in two passes to get O(n) time and space. Then there’s a two-pointer approach that gets O(1) space.

Interviewer: Walk me through the two-pointer logic.

Candidate: I place one pointer at each end. At each step, I compare height[left] and height[right]. If left is shorter or equal, the left side is the binding constraint. The water at left is capped by max_left, regardless of what’s on the right. I process it, update max_left, and advance left inward. The right side is symmetric. Both pointers move inward exactly once, giving O(n) total steps.

Interviewer: Why does it not matter what the right maximum is when processing the left pointer?

Candidate: Because height[left] <= height[right] guarantees the right side is at least as tall as the current left bar. Since water is bounded by the minimum of both sides, and the left maximum is the smaller bound, the exact right maximum doesn’t change the water at left. Even if there’s a taller bar further right, it can only increase max_right, which doesn’t affect the formula when max_left < max_right already.

Interviewer: How would you extend this to a 2D elevation map?

Candidate: In 2D, water flows to the lowest boundary cell. The optimal approach uses a min-heap seeded with all boundary cells. At each step, pop the lowest-height boundary cell and any interior neighbor shorter than it gets flooded to that height. Push updated neighbors back into the heap. This is essentially Dijkstra’s algorithm applied to water flow, running in O(m x n x log(m x n)) time.

Trapping Rain Water sits at the intersection of two-pointer technique, prefix/suffix arrays, and geometric reasoning:

The jump from Trapping Rain Water to Container With Most Water (#11) is one of the most common interview progressions. Both use two pointers converging from the ends, but with subtly different advancement rules.

Practice This in a Mock Interview

This walkthrough gives you three complete approaches, the geometric derivation, and the two-pointer invariant explained precisely. But Trapping Rain Water has a well-earned reputation for tripping up candidates who understood the solution perfectly while reading and then confused the pointer advancement rule, forgot to update the running maximum, or couldn’t justify the two-pointer logic when probed mid-implementation.

The two-pointer solution is elegant but fragile to misremembering. The only way to make the invariant feel genuinely internalized is to derive it from scratch, trace it through an example, and explain it out loud to someone asking follow-up questions.

Start a mock interview for Trapping Rain Water on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →