How to Explain Trapping Rain Water in a Coding Interview (Step-by-Step)

Trapping Rain Water is one of the most iconic Hard problems in coding interviews. There are three valid approaches — brute force, prefix arrays, and two pointers — and knowing all three, plus how they relate to each other, is what makes a candidate stand out.

In this post, you’ll learn exactly how to walk an interviewer through this problem: the core formula, why the two-pointer approach works, and which edge cases to call out proactively.

Problem Statement

Examples

Constraints

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

What Is the Problem?

“I have an elevation map as an array of bar heights. After rain, water collects in the valleys between taller bars. I need to compute the total volume of water trapped — treating each index as a column of width 1.”

The Core Formula — Water at Each Cell

Explain this formula before touching any approach. Once the interviewer understands it, every approach is just a different way to compute max_left and max_right efficiently.

Step 1: Walk Through All Three Approaches

Approach 2 — Prefix Arrays (Explain First, Code Second)

“I precompute two arrays — max_left[i] is the tallest bar from index 0 to i, and max_right[i] is the tallest bar from i to n-1. Then for each cell I apply the formula. This is O(n) time and O(n) space — a clean stepping stone to the optimal solution.”

def trap(height: List[int]) -> int:
    n = len(height)
    max_left  = [0] * n
    max_right = [0] * n

    # Fill max_left — running max from left to right
    max_left[0] = height[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i-1], height[i])

    # Fill max_right — running max from right to left
    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])

    # Apply formula at each cell
    total = 0
    for i in range(n):
        total += max(0, min(max_left[i], max_right[i]) - height[i])

    return total

Approach 3 — Two Pointers (Optimal, Lead With This)

“If max_left <= max_right, the left side is the bottleneck. Water at the left pointer is max_left - height[left]. We add it and move left forward. Otherwise we do the same for the right pointer. We never need to look the other way.”

The Code — Two Pointer Solution

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_left, max_right = 0, 0   # Running max walls on each side
        total = 0

        while left < right:
            if height[left] <= height[right]:
                # Left side is the bottleneck — process it
                if height[left] >= max_left:
                    max_left = height[left]  # New max wall — no water here
                else:
                    total += max_left - height[left]  # Water above this cell
                left += 1
            else:
                # Right side is the bottleneck — process it
                if height[right] >= max_right:
                    max_right = height[right]  # New max wall — no water here
                else:
                    total += max_right - height[right]  # Water above this cell
                right -= 1

        return total

Key thing to point out: max_left and max_right are single integers — not arrays. That’s what drops space from O(n) to O(1).

Visual Walkthrough

Using height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] — total water = 6:

Water per cell — applying the formula at each index:

Step 5: Highlight Edge Cases

Step 6: State Time and Space Complexity

“The two-pointer solution is strictly better than the prefix array approach — same O(n) time but O(1) space instead of O(n). Each element is processed exactly once as the pointers converge from both ends.”

Interview Checklist for Trapping Rain Water

• Restate — “total water trapped = sum of water above each bar”
• State the formula — water[i] = max(0, min(max_left, max_right) - height[i])
• Present all three approaches — brute force, prefix arrays, two pointers
• Explain prefix arrays first — it’s the clearest path to understanding
• Explain the two-pointer insight — process the side with the smaller max wall
• Clarify that max_left and max_right are single integers, not arrays
• Handle monotonic array — no water possible, formula gives 0
• Handle single/two element — loop doesn’t run or yields 0
• State O(n²) → O(n)/O(n) → O(n)/O(1) progression clearly
• Ask before coding, don’t just dive in

Related Problems to Practice

If you can solve Trapping Rain Water cleanly, try these next: