Interview Problem

Trapping Rain Water

“The Rooftop Plumber”

Time: O(n)

Space: O(1)

Difficulty: Hard

Pattern: Two Pointers

History

This problem is a classic because it looks like "just add some water" until you realize you're really solving local minima with global boundaries. It shows up in interviews because it tests whether you can:

reason about constraints
avoid overcounting
choose the right strategy (not brute-force panic)

Think of the bars as buildings. After it rains, water collects in the dips... but only if there are taller buildings on both sides. It's a beautiful problem that bridges visual intuition with algorithmic elegance.

Problem Definition

You're given an array of non-negative integers where each value represents a bar height. Each bar has width 1.

Return how much rainwater can be trapped after raining.

Rule of the universe

Water at position $i$ depends on the tallest wall on the left and the tallest wall on the right.

Core Idea

At any index $i$ :

$water[i] = max(0, min(maxLeft[i], maxRight[i]) - height[i])$

That's it. Everything else is just *how efficiently you compute it*.

How It Works

The Two Pointers approach is the optimal solution. It uses the key insight that water level at any position is bounded by the shorter of the two maximum boundaries.

The Algorithm Step-by-Step

Initialize: Two pointers at the extremes ( $l = 0$ , $r = n-1$ ) and track $maxLeft$ and $maxRight$ .
Compare: Check which side has the smaller maximum.
Process Smaller Side: If $height[l] \leq height[r]$ , process the left side:
- Move $l$ inward
- If current height > $maxLeft$ , update $maxLeft$ (no water here)
- Otherwise, add $maxLeft - height[l]$ to total water
Mirror for Right: Same logic, mirrored for the right pointer.
Repeat: Continue until pointers meet.

The Shrinking Window

We shrink from both ends. At each step, we resolve the side with the smaller boundary because that's the side we can fully compute—the other side is guaranteed to have a wall at least as tall.

Time ComplexityO(n)

Single pass through the array with two pointers moving inward. Each element is visited exactly once.

Space ComplexityO(1)

Only four variables needed: two pointers and two running maximums. No auxiliary data structures.

Approaches

Brute Force

Time: O(n²)Space: O(1)

For each index, scan left for max and scan right for max, then compute water at that position.

Prefix/Suffix Arrays (DP)

Time: O(n)Space: O(n)

Precompute maxLeft[i] and maxRight[i] arrays, then compute water in one pass.

Two PointersOptimal

Time: O(n)Space: O(1)

Use two pointers shrinking inward, tracking running max on each side. Process the side with smaller max.

Monotonic Stack

Time: O(n)Space: O(n)

Use a decreasing stack of indices. When finding a taller bar, compute trapped water in the valley formed.

Why It Works

Here's the invariant that makes Two Pointers valid:

Water level is capped by the shorter side boundary.
When $height[l] \leq height[r]$ , you *already know* the right side has at least a boundary as tall as $height[l]$ (because $height[r]$ is taller or equal *right now*).
So the trapped water at $l$ depends only on $maxLeft$ .

Meaning

- If $height[l] < maxLeft$ , you can add $maxLeft - height[l]$ . - Otherwise update $maxLeft$ .

Same logic mirrored on the right. This prevents overthinking, avoids backtracking, and guarantees linear time.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def trap(height: list[int]) -> int:
2    """Calculate trapped rainwater using two pointers."""
3    if not height:
4        return 0
5
6    left, right = 0, len(height) - 1
7    max_left, max_right = 0, 0
8    total_water = 0
9
10    while left < right:
11        # Process the side with smaller boundary
12        if max_left <= max_right:
13            left += 1
14            h = height[left]
15
16            if h > max_left:
17                # New max found - no water here
18                max_left = h
19            else:
20                # Water trapped = max_left - current height
21                total_water += max_left - h
22        else:
23            right -= 1
24            h = height[right]
25
26            if h > max_right:
27                # New max found - no water here
28                max_right = h
29            else:
30                # Water trapped = max_right - current height
31                total_water += max_right - h
32
33    return total_water

Python • .py

Real World Use Cases

1Elevation and flood modeling (simplified 1D version)
2Histogram-based signal smoothing
3Memory allocation and capacity planning intuition (peaks define constraints, valleys are unused capacity)
4Gateway to 2D/3D geometry problems
5Water distribution system analysis

Key Insights

The trapped water at each index depends on global boundaries, not local neighbors.
Two Pointers works because you resolve the currently shorter side.
The problem is really: how much empty space exists under a 'ceiling' formed by boundary maxima.
Stack solution teaches you how to compute 'valleys' once a right boundary appears.
The formula $min(maxLeft, maxRight) - height$ captures the physics of water settling.

When to Use

Use the Two Pointers approach when you need maximum efficiency and memory matters. It's the cleanest interview answer and demonstrates strong algorithmic intuition. The prefix/suffix approach is fine for clarity when explaining to beginners.

When NOT to Use

Don't overcomplicate it when the array is tiny and prefix/suffix is fine. Also don't confuse this with the 2D Trapping Rain Water problem—that one requires BFS/priority queue and is a different beast entirely.

Common Interview Pitfalls

Forgetting $max(0, ...)$ and subtracting into negative water.
Thinking the water depends on 'nearest taller wall' instead of 'tallest wall'.
Off-by-one mistakes in the stack width calculation.
Trying to simulate actual water filling (way too slow and messy).
Processing the wrong pointer (must process the side with smaller max).

Interview Questions & Answers

Why does min(maxLeft, maxRight) determine the water level?

Because water spills over the shorter boundary first. The taller boundary doesn't matter until the shorter one increases.

Why can Two Pointers decide a side greedily?

Because the shorter side is the limiting factor. When left height is smaller, the right side already guarantees a boundary tall enough to resolve left safely.

Which solution should you present first in an interview?

Start with brute force to show understanding, then immediately upgrade to prefix/suffix, then deliver Two Pointers as the optimal.

When would you choose the stack solution?

When you want to reuse the monotonic stack pattern for similar problems (largest rectangle, daily temps, next greater element).

What's the difference between this and Container With Most Water?

Container With Most Water finds the max area between two lines. Trapping Rain Water sums all water trapped across the entire elevation map. Similar two-pointer approach, different computation.

Related Algorithms

Pathfinding

Dijkstra's Algorithm

similar boundary computation pattern

O((V + E) log V)

Pathfinding

Breadth-First Search

2D water trapping uses BFS

O(V + E)

Trees

Max Heap

stack solution uses similar data structure thinking

O(n)

Watch Trapping Rain Water in Action