Trapping Rain Water (LeetCode

Learn how to solve Trapping Rain Water using brute force, prefix/suffix arrays, and the optimal two-pointer approach. Includes intuition, dry runs, Java code, correctness proof, complexity analysis, edge cases, interview tips, and production applications.

Introduction

Trapping Rain Water (LeetCode #42) is one of the most celebrated hard-level problems in coding interviews.

It is frequently asked at companies like:

Google
Amazon
Microsoft
Meta
Apple
Netflix
Uber
Goldman Sachs

Interviewers use this problem to evaluate whether a candidate can:

Reason about water trapped between barriers
Optimize from O(n²) brute force to O(n) with prefix arrays
Further optimize to O(n) time and O(1) space using Two Pointers
Explain the invariant behind the Two Pointer approach convincingly

The key insight is:

The water above any bar is determined by the minimum of the maximum height to its left and the maximum height to its right, minus its own height.

For each index i:

water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])

The Two Pointer approach computes this without storing the full prefix and suffix arrays, by maintaining running maximums from both ends.

Problem Statement

Given an array height of n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Return the total units of trapped water.

Formula

Water trapped above each bar:

water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])

Total water:

sum of water[i] for all i

Example 1

Input

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

Output

6

Explanation:

The elevation map traps 6 units of rain water.

Between index 2 and index 7, water is trapped at several positions.

Example 2

Input

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

Output

9

Explanation:

index 1: min(4, 5) - 2 = 2
index 2: min(4, 5) - 0 = 4
index 3: min(4, 5) - 3 = 1
index 4: min(4, 5) - 2 = 2

Total = 2 + 4 + 1 + 2 = 9

Example 3

Input

height = [3, 0, 2, 0, 4]

Output

7

Explanation:

index 1: min(3, 4) - 0 = 3
index 2: min(3, 4) - 2 = 1
index 3: min(3, 4) - 0 = 3

Total = 3 + 1 + 3 = 7

Important Problem Guarantees

The LeetCode problem guarantees:

n >= 1
0 <= height[i] <= 100,000
No negative heights.
A single bar or two bars trap no water — valid water requires at least one bar on each side.

Core Intuition

Imagine standing at any bar.

Water can only be trapped above that bar if there is a taller (or equal) bar to both its left and its right.

The water level above that bar is:

min(tallest bar to the left, tallest bar to the right)

The actual water above the bar is that level minus the bar's own height.

If the bar is taller than the water level, no water is trapped (result is 0).

graph TD
    Bar_at_index_i["Bar at index i"] --> Water_level_min_leftMax_righ["Water level = min(leftMax, rightMax)"]
    Water_level_min_leftMax_righ["Water level = min(leftMax, rightMax)"] --> Water_trapped_max_0_waterLev["Water trapped = max(0, waterLevel - height(i))"]

Approach 1 — Brute Force

Core Idea

For each bar at index i:

Scan left to find the maximum height to the left.
Scan right to find the maximum height to the right.
Compute the water trapped above this bar.

Sum all contributions.

Java Code — Brute Force

public class TrappingRainWaterBruteForce {

    public int trap(int[] height) {

        int totalWater = 0;
        int n = height.length;

        for (int i = 1; i < n - 1; i++) {

            int leftMax = 0;
            for (int left = 0; left <= i; left++) {
                leftMax = Math.max(leftMax, height[left]);
            }

            int rightMax = 0;
            for (int right = i; right < n; right++) {
                rightMax = Math.max(rightMax, height[right]);
            }

            int waterAbove =
                    Math.min(leftMax, rightMax)
                    - height[i];

            totalWater += waterAbove;

        }

        return totalWater;

    }

}

Brute Force Complexity

Complexity	Value
Time	O(n²)
Space	O(1)

For each of n bars, two inner scans each up to n steps.

At LeetCode constraints (n up to 100,000), this exceeds the time limit.

Why Brute Force Is Inefficient

For:

n = 100,000

the number of inner scan steps is approximately:

100,000 × 100,000 = 10 billion operations

The left and right maximums for every index are recomputed from scratch each time, even though adjacent indices share most of the scan.

Approach 2 — Prefix and Suffix Arrays

Core Idea

Precompute:

leftMax[i] — maximum height from index 0 to i (inclusive).
rightMax[i] — maximum height from index i to n-1 (inclusive).

Then compute trapped water in a single pass.

Algorithm

Build leftMax array:
    leftMax[0] = height[0]
    leftMax[i] = max(leftMax[i-1], height[i])

Build rightMax array:
    rightMax[n-1] = height[n-1]
    rightMax[i] = max(rightMax[i+1], height[i])

For each i:
    water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])

Return sum of water[]

Java Code — Prefix and Suffix Arrays

public class TrappingRainWaterPrefixSuffix {

    public int trap(int[] height) {

        int n = height.length;
        if (n < 3) return 0;

        int[] leftMax  = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int totalWater = 0;
        for (int i = 1; i < n - 1; i++) {
            int waterLevel =
                    Math.min(leftMax[i], rightMax[i]);
            totalWater +=
                    Math.max(0, waterLevel - height[i]);
        }

        return totalWater;

    }

}

Prefix/Suffix Complexity

Complexity	Value
Time	O(n)
Space	O(n)

Three linear passes and two arrays of size n.

This is the most intuitive O(n) approach, but uses O(n) space.

Why Not Always Use Prefix Arrays?

The prefix/suffix approach is correct but uses two extra arrays.

For:

n = 100,000,000 integers

two arrays of int require:

2 × 100,000,000 × 4 bytes = 800 MB

This is unacceptable in memory-constrained environments.

The Two Pointer approach achieves the same O(n) time with O(1) space.

Approach 3 — Optimal Two Pointer Solution

Core Idea

Instead of precomputing all left and right maximums, maintain two running variables:

int leftMax  = 0;
int rightMax = 0;

Use two pointers — one starting from the left, one from the right — converging inward.

At each step, process the side with the smaller maximum.

If leftMax <= rightMax:
    water[left] = leftMax - height[left]  (safe: right side is >= leftMax)
    left++

Else:
    water[right] = rightMax - height[right]  (safe: left side is >= rightMax)
    right--

Why This Is Safe

When leftMax <= rightMax:

The water above height[left] is bounded by leftMax (the smaller side).

We do not need to know the exact rightMax beyond the current position —
we already know it is at least as tall as leftMax.

So water[left] = max(0, leftMax - height[left]) is exact.

When rightMax < leftMax:

The water above height[right] is bounded by rightMax (the smaller side).

We already know the left side is at least as tall as rightMax.

So water[right] = max(0, rightMax - height[right]) is exact.

This is the key invariant that makes the Two Pointer approach correct.

Algorithm

graph TD
    left_0["left  = 0"] --> right_n_1["right = n - 1"]
    right_n_1["right = n - 1"] --> leftMax_0["leftMax  = 0"]
    leftMax_0["leftMax  = 0"] --> rightMax_0["rightMax = 0"]
    rightMax_0["rightMax = 0"] --> total_0["total = 0"]
    total_0["total = 0"] --> Loop_while_left_right["Loop while left  right:"]
    Loop_while_left_right["Loop while left  right:"] --> height_left_height_right["height(left) = height(right)"]
    height_left_height_right["height(left) = height(right)"] --> Yes["Yes →"]
    Yes["Yes →"] --> leftMax_max_leftMax_height_l["leftMax = max(leftMax, height(left))"]
    leftMax_max_leftMax_height_l["leftMax = max(leftMax, height(left))"] --> total_max_0_leftMax_height_l["total  += max(0, leftMax - height(left))"]
    total_max_0_leftMax_height_l["total  += max(0, leftMax - height(left))"] --> left["left++"]
    left["left++"] --> No["No  →"]
    No["No  →"] --> rightMax_max_rightMax_height["rightMax = max(rightMax, height(right))"]
    rightMax_max_rightMax_height["rightMax = max(rightMax, height(right))"] --> total_max_0_rightMax_height_["total   += max(0, rightMax - height(right))"]
    total_max_0_rightMax_height_["total   += max(0, rightMax - height(right))"] --> right["right--"]
    right["right--"] --> Return_total["Return total"]

Java Code — Optimal Two Pointer Solution

public class TrappingRainWater {

    public int trap(int[] height) {

        int left     = 0;
        int right    = height.length - 1;
        int leftMax  = 0;
        int rightMax = 0;
        int total    = 0;

        while (left < right) {

            if (height[left] <= height[right]) {

                leftMax = Math.max(leftMax, height[left]);
                total  += leftMax - height[left];
                left++;

            } else {

                rightMax = Math.max(rightMax, height[right]);
                total   += rightMax - height[right];
                right--;

            }

        }

        return total;

    }

}

LeetCode-Style Implementation

public class Solution {

    public int trap(int[] height) {

        int left  = 0;
        int right = height.length - 1;
        int lMax  = 0;
        int rMax  = 0;
        int water = 0;

        while (left < right) {

            if (height[left] <= height[right]) {
                lMax  = Math.max(lMax, height[left]);
                water += lMax - height[left];
                left++;
            } else {
                rMax  = Math.max(rMax, height[right]);
                water += rMax - height[right];
                right--;
            }

        }

        return water;

    }

}

Two Pointer Flow

graph TD
    Initialize_left_0_right_n_1["Initialize left = 0, right = n-1"] --> leftMax_0_rightMax_0_total_0["leftMax = 0, rightMax = 0, total = 0"]
    leftMax_0_rightMax_0_total_0["leftMax = 0, rightMax = 0, total = 0"] --> left_right["left  right?"]
    left_right["left  right?"] --> Yes["Yes ↓"]
    Yes["Yes ↓"] --> height_left_height_right["height(left) = height(right)?"]
    height_left_height_right["height(left) = height(right)?"] --> Yes1["Yes →"]
    Yes1["Yes →"] --> Update_leftMax["Update leftMax"]
    Update_leftMax["Update leftMax"] --> Add_leftMax_height_left_to_t["Add (leftMax - height(left)) to total"]
    Add_leftMax_height_left_to_t["Add (leftMax - height(left)) to total"] --> left["left++"]
    left["left++"] --> No["No →"]
    No["No →"] --> Update_rightMax["Update rightMax"]
    Update_rightMax["Update rightMax"] --> Add_rightMax_height_right_to["Add (rightMax - height(right)) to total"]
    Add_rightMax_height_right_to["Add (rightMax - height(right)) to total"] --> right["right--"]
    right["right--"] --> Repeat["Repeat"]

Detailed Dry Run

Input:

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

Initial state:

left  = 0
right = 11
leftMax  = 0
rightMax = 0
total = 0

Iteration 1

height[left]  = 0
height[right] = 1

0 <= 1 → process left

leftMax = max(0, 0) = 0
water   = 0 - 0 = 0
total   = 0

left = 1

Iteration 2

height[left]  = 1
height[right] = 1

1 <= 1 → process left

leftMax = max(0, 1) = 1
water   = 1 - 1 = 0
total   = 0

left = 2

Iteration 3

height[left]  = 0
height[right] = 1

0 <= 1 → process left

leftMax = max(1, 0) = 1
water   = 1 - 0 = 1
total   = 1

left = 3

Iteration 4

height[left]  = 2
height[right] = 1

2 > 1 → process right

rightMax = max(0, 1) = 1
water    = 1 - 1 = 0
total    = 1

right = 10

Iteration 5

height[left]  = 2
height[right] = 2

2 <= 2 → process left

leftMax = max(1, 2) = 2
water   = 2 - 2 = 0
total   = 1

left = 4

Iteration 6

height[left]  = 1
height[right] = 2

1 <= 2 → process left

leftMax = max(2, 1) = 2
water   = 2 - 1 = 1
total   = 2

left = 5

Iteration 7

height[left]  = 0
height[right] = 2

0 <= 2 → process left

leftMax = max(2, 0) = 2
water   = 2 - 0 = 2
total   = 4

left = 6

Iteration 8

height[left]  = 1
height[right] = 2

1 <= 2 → process left

leftMax = max(2, 1) = 2
water   = 2 - 1 = 1
total   = 5

left = 7

Iteration 9

height[left]  = 3
height[right] = 2

3 > 2 → process right

rightMax = max(1, 2) = 2
water    = 2 - 2 = 0
total    = 5

right = 9

Iteration 10

height[left]  = 3
height[right] = 1

3 > 1 → process right

rightMax = max(2, 1) = 2
water    = 2 - 1 = 1
total    = 6

right = 8

left = 7, right = 8 → left < right → one more step.

Iteration 11

height[left]  = 3
height[right] = 2

3 > 2 → process right

rightMax = max(2, 2) = 2
water    = 2 - 2 = 0
total    = 6

right = 7

left = 7, right = 7 → loop ends.

Return:

Dry Run Table

left	right	h[L]	h[R]	lMax	rMax	water added	total
0	11	0	1	0	0	0	0
1	11	1	1	1	0	0	0
2	11	0	1	1	0	1	1
3	11	2	1	1	1	0	1
3	10	2	2	2	1	0	1
4	10	1	2	2	1	1	2
5	10	0	2	2	1	2	4
6	10	1	2	2	1	1	5
7	10	3	2	2	2	0	5
7	9	3	1	2	2	1	6
7	8	3	2	2	2	0	6

Return 6.

Visual Representation

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
index     0  1  2  3  4  5  6  7  8  9 10 11

      |
   3  |              |
   2  |     |     |  |  |     |
   1  |  |  |  |  |  |  |  |  |
   0  +--+--+--+--+--+--+--+--+--+--+--+--

Water trapped (shown as ~):

      |
   3  |              |
   2  |     |  ~~ |  |  |     |
   1  |  |  ~~ |  ~~ |  |  |  |
   0  +--+--+--+--+--+--+--+--+--+--+--+--

Total = 6 units

Why the Two Pointer Approach Is Correct

Claim: When height[left] <= height[right], the water above height[left] is exactly leftMax - height[left].

Proof:

The water level above any bar is min(leftMax, rightMax).

When height[left] <= height[right]:

The right pointer has seen a bar of height >= height[left].

rightMax >= height[right] >= height[left] >= leftMax (since leftMax is built incrementally).

Therefore: min(leftMax, rightMax) = leftMax.

Water above left = leftMax - height[left].

No matter what bars lie between left and right, the right side is already proven to be at least as tall as leftMax.

The symmetric argument holds when height[right] < height[left].

Correctness Proof

Invariant:

At every step:

Every index processed on the left has its exact water contribution computed.
Every index processed on the right has its exact water contribution computed.
The optimal pair [left, right] is always within the current window.

Base case: Before the loop, leftMax = 0 and rightMax = 0. No water has been processed yet.

Inductive step:

When height[left] <= height[right]: the minimum boundary for left is leftMax (proven above). The contribution leftMax - height[left] is exact. left is advanced.
When height[right] < height[left]: the minimum boundary for right is rightMax (symmetric argument). The contribution rightMax - height[right] is exact. right is advanced.

Termination: At each step, either left or right advances. The loop terminates when left == right.

Conclusion: All bars have been processed with exact water contributions. The total is correct.

Loop Invariant

At every iteration:

total = sum of exact water contributions
        for all indices already processed

leftMax  = max height seen from the left so far
rightMax = max height seen from the right so far

The unprocessed interval is [left, right].

When the loop ends:

left == right
All indices have been processed.
total is the answer.

Complexity Analysis

Complexity	Value
Time	O(n)
Space	O(1)

Each pointer moves at most n - 1 steps.

Only four integer variables are maintained — no arrays.

Why the Complexity Is Not O(n²)

The two pointers converge from both ends.

At each iteration, exactly one pointer advances.

Total iterations:

right - left ≤ n - 1 → O(n)

There is no nested scan.

Approach Comparison

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Recomputes max for every bar
Prefix/Suffix Arrays	O(n)	O(n)	Three passes, two extra arrays
Two Pointer	O(n)	O(1)	Optimal — single pass, running maximums

Production-Ready Implementation

import java.util.Objects;

public class TrappingRainWater {

    /**
     * Computes the total water trapped between bars.
     *
     * @param height non-null array of non-negative integers
     * @return total units of trapped water
     * @throws NullPointerException if height is null
     */
    public int trap(int[] height) {

        Objects.requireNonNull(height,
                "height must not be null");

        if (height.length < 3) {
            return 0;
        }

        int left     = 0;
        int right    = height.length - 1;
        int leftMax  = 0;
        int rightMax = 0;
        int total    = 0;

        while (left < right) {

            if (height[left] <= height[right]) {

                leftMax = Math.max(leftMax, height[left]);
                total  += leftMax - height[left];
                left++;

            } else {

                rightMax = Math.max(rightMax, height[right]);
                total   += rightMax - height[right];
                right--;

            }

        }

        return total;

    }

}

Edge Cases

Empty or Single Bar

Input

height = []
height = [5]

Output

0

No water can be trapped without at least one bar on each side.

Two Bars

Input

height = [3, 5]

Output

0

No bar between two walls — nothing to trap water above.

All Same Height (Flat)

Input

height = [3, 3, 3, 3]

Output

0

Water level equals bar height at every position. No water trapped.

Monotonically Increasing

Input

height = [1, 2, 3, 4, 5]

Output

0

The right wall is always taller. The left wall is always the constraint — but there is no depression to hold water.

Monotonically Decreasing

Input

height = [5, 4, 3, 2, 1]

Output

0

No bar can hold water — every bar's right side has no taller wall.

Single Valley

Input

height = [3, 0, 3]

Output

3

index 1: min(3, 3) - 0 = 3

Large Valley

Input

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

Output

9

Left wall is 4, right wall is 5. Water fills from index 1 to 4.

Bars of Zero Height

Input

height = [0, 0, 0, 0]

Output

0

No walls — no water trapped.

Asymmetric Walls

Input

height = [1, 0, 5]

Output

1

index 1: min(1, 5) - 0 = 1

The shorter left wall limits the water level.

Common Interview Mistakes

Mistake 1 — Using height[left] as leftMax Without Updating

❌  total += height[left] - height[left];  // always 0

leftMax must track the running maximum, not the current height.

Mistake 2 — Not Taking max(0, ...) for Water

If a bar is taller than leftMax or rightMax:

leftMax - height[left] could be negative

In the Two Pointer approach, updating leftMax = max(leftMax, height[left]) before subtracting guarantees the result is always non-negative.

No explicit max(0, ...) is needed because leftMax >= height[left] always holds after the update.

Mistake 3 — Processing Both Pointers in the Same Iteration

❌  left++;
    right--;

Only one pointer should move per iteration, depending on which side has the smaller maximum.

Mistake 4 — Starting Inner Scans at 0 and n-1 (Brute Force)

The first and last bars can never trap water — they have no wall on one side.

Skip indices 0 and n-1 in the brute force scan.

Mistake 5 — Confusing With Container With Most Water

Container With Most Water:

Area = min(height[left], height[right]) × width
Goal: maximize this area

Trapping Rain Water:

Water above bar i = min(leftMax, rightMax) - height[i]
Goal: sum of water above all bars

Different formula, different goal, different pointer movement logic.

Mistake 6 — Claiming O(n) for the Brute Force

The brute force has two nested loops — each bar scans all bars to its left and right.

Total inner scan steps ≈ n²

Mistake 7 — Not Handling Arrays Shorter Than 3

An array of length 1 or 2 cannot trap any water. Always return 0 early.

Mistake 8 — Updating leftMax After Adding Water

❌  total   += leftMax - height[left];
    leftMax  = Math.max(leftMax, height[left]);

leftMax must be updated before computing the water contribution.

Correct:

leftMax = Math.max(leftMax, height[left]);
total  += leftMax - height[left];

Follow-Up 1 — What Is the Maximum Possible Water?

Given constraints height[i] ≤ 100,000 and n ≤ 100,000:

Max water per bar ≈ 100,000

Max bars ≈ 100,000

Max total water ≈ 10^10

This exceeds int range (~2.1 × 10^9).

Use long for the total in production code to be safe:

long total = 0;

Follow-Up 2 — Return the Water Trapped Above Each Bar

Instead of summing, collect per-bar contributions:

public int[] waterPerBar(int[] height) {

    int n = height.length;
    int[] leftMax  = new int[n];
    int[] rightMax = new int[n];
    int[] water    = new int[n];

    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    for (int i = 0; i < n; i++) {
        water[i] = Math.max(
                0,
                Math.min(leftMax[i], rightMax[i]) - height[i]);
    }

    return water;

}

This uses the prefix/suffix approach for per-bar output.

Follow-Up 3 — What If Height Values Can Be Very Large?

Use long for intermediate computations:

long total = 0;

leftMax  = Math.max(leftMax, height[left]);
total   += (long) (leftMax - height[left]);

This prevents integer overflow when water volumes are large.

Follow-Up 4 — Solve Using a Monotonic Stack

The stack approach processes bars as they are encountered:

Maintain a stack of indexes in decreasing height order.

When a taller bar is encountered:
    Pop the shorter bar (the valley floor).
    Compute water between the new bar and the bar now on top of the stack.
    Add to total.

Time  → O(n)
Space → O(n)

The stack approach is more complex to implement but useful when you need to also identify which specific bars form each water pocket.

Follow-Up 5 — Streaming or Online Input

The Two Pointer approach requires the full array in memory.

For a streaming case, use the prefix/suffix approach with a two-pass algorithm:

Pass 1 (left to right): Build leftMax.
Pass 2 (right to left): Compute water using rightMax on the fly.

Or buffer the full stream before processing.

Production Applications

The rain water trapping principle appears in real engineering systems.

Examples include:

Histogram-based capacity analysis (e.g., buffer pool, memory allocation)
Network traffic shaping — identifying bandwidth valleys between peaks
Reservoir simulation and watershed modelling
Terrain analysis for drainage and flood modelling
Financial chart analysis — identifying consolidation zones between price peaks
CPU utilization gap analysis between load spikes
Cloud auto-scaling — identifying compute capacity valleys in time-series data

The core insight — the water level at any point is constrained by the minimum of the two surrounding maximums — generalizes to many constraint-based capacity problems.

Real-World Example — Memory Buffer Pool Analysis

A memory allocator tracks free block sizes over time.

The "trapped water" analogy maps to available contiguous memory between large allocations.

public long analyseBufferCapacity(int[] blockSizes) {

    if (blockSizes == null
            || blockSizes.length < 3) {
        return 0L;
    }

    int  left     = 0;
    int  right    = blockSizes.length - 1;
    int  leftMax  = 0;
    int  rightMax = 0;
    long total    = 0L;

    while (left < right) {

        if (blockSizes[left]
                <= blockSizes[right]) {

            leftMax = Math.max(
                    leftMax, blockSizes[left]);
            total  += leftMax - blockSizes[left];
            left++;

        } else {

            rightMax = Math.max(
                    rightMax, blockSizes[right]);
            total   += rightMax - blockSizes[right];
            right--;

        }

    }

    return total;

}

Real-World Example — Terrain Drainage Volume

Given elevation data as an array, compute the total volume of water retained after heavy rainfall:

elevation = [3, 1, 2, 4, 0, 1, 3, 2]

Total retained volume = trap(elevation)

This is directly the Trapping Rain Water problem applied to terrain data.

Senior-Level Discussion — Why Does This Work Without Storing Both Arrays?

The prefix/suffix approach requires both leftMax[i] and rightMax[i] to be known simultaneously for each bar.

The Two Pointer approach avoids this by using a critical observation:

When we process the left side, we only need leftMax.

We do not need the exact rightMax value because we already know:
  height[right] >= height[left]
  therefore rightMax >= height[right] >= leftMax
  therefore min(leftMax, rightMax) = leftMax

The decision of which pointer to move gives us the exact water contribution without needing the other side's maximum.

This is a lazy evaluation strategy — compute exactly what you need, when you need it.

Senior-Level Discussion — Is This Dynamic Programming?

The prefix/suffix approach is a form of dynamic programming — it builds two tables bottom-up.

The Two Pointer approach is a greedy algorithm — it makes a locally optimal decision at each step (process the side with the smaller maximum) and provably produces the globally optimal answer.

Senior-Level Discussion — Can the Stack Approach Beat Two Pointers?

No.

Both the stack and two-pointer approaches achieve O(n) time.

The stack uses O(n) space; the two-pointer uses O(1) space.

The two-pointer approach is strictly better in space complexity.

The stack is preferred only when you need to identify the specific bar pairs forming each water pocket (for debugging or visualization).

Interview Explanation

A strong interview walkthrough:

graph TD
    N_1_0_0["1"] --> N_2_1_1["2"]
    N_1_0_0["1"] --> Walk_1_2["Walk"]
    Explain_0_1["Explain"] --> through_1_3["through"]
    Explain_0_1["Explain"] --> brute_1_4["brute"]
    the_0_2["the"] --> force_1_5["force"]
    the_0_2["the"] --> and_1_6["and"]
    per_bar_0_3["per-bar"] --> explain_1_7["explain"]
    per_bar_0_3["per-bar"] --> why_1_8["why"]
    water_0_4["water"] --> it_1_9["it"]
    water_0_4["water"] --> is_1_10["is"]
    formula_0_5["formula"] --> O_1_11["O"]
    formula_0_5["formula"] --> n_1_12["n²"]
    N_2_1_1["2"] --> N_3_2_1["3"]
    N_2_1_1["2"] --> Explain_2_2["Explain"]
    Walk_1_2["Walk"] --> the_2_3["the"]
    Walk_1_2["Walk"] --> prefix_2_4["prefix"]
    through_1_3["through"] --> suffix_2_5["suffix"]
    through_1_3["through"] --> optimization_2_6["optimization"]
    brute_1_4["brute"] --> to_2_7["to"]
    brute_1_4["brute"] --> O_2_8["O"]
    force_1_5["force"] --> n_2_9["n"]
    force_1_5["force"] --> time_2_10["time"]
    and_1_6["and"] --> O_2_11["O"]
    and_1_6["and"] --> n_2_12["n"]
    explain_1_7["explain"] --> space_2_13["space"]
    N_3_2_1["3"] --> N_4_3_1["4"]
    N_3_2_1["3"] --> Explain_3_2["Explain"]
    Explain_2_2["Explain"] --> why_3_3["why"]
    Explain_2_2["Explain"] --> the_3_4["the"]
    the_2_3["the"] --> Two_3_5["Two"]
    the_2_3["the"] --> Pointer_3_6["Pointer"]
    prefix_2_4["prefix"] --> approach_3_7["approach"]
    prefix_2_4["prefix"] --> can_3_8["can"]
    suffix_2_5["suffix"] --> avoid_3_9["avoid"]
    suffix_2_5["suffix"] --> the_3_10["the"]
    optimization_2_6["optimization"] --> extra_3_11["extra"]
    optimization_2_6["optimization"] --> arrays_3_12["arrays"]
    N_4_3_1["4"] --> N_5_4_1["5"]
    N_4_3_1["4"] --> State_4_2["State"]
    Explain_3_2["Explain"] --> the_4_3["the"]
    Explain_3_2["Explain"] --> key_4_4["key"]
    why_3_3["why"] --> invariant_4_5["invariant"]
    why_3_3["why"] --> when_4_6["when"]
    the_3_4["the"] --> height_4_7["height"]
    the_3_4["the"] --> left_4_8["left"]
    Two_3_5["Two"] --> height_4_9["height"]
    Two_3_5["Two"] --> right_4_10["right"]
    N_5_4_1["5"] --> the_5_1["the"]
    N_5_4_1["5"] --> water_5_2["water"]
    State_4_2["State"] --> level_5_3["level"]
    State_4_2["State"] --> at_5_4["at"]
    the_4_3["the"] --> left_5_5["left"]
    the_4_3["the"] --> is_5_6["is"]
    key_4_4["key"] --> exactly_5_7["exactly"]
    key_4_4["key"] --> leftMax_5_8["leftMax"]
    the_5_1["the"] --> N_6_6_1["6"]
    the_5_1["the"] --> Walk_6_2["Walk"]
    water_5_2["water"] --> through_6_3["through"]
    water_5_2["water"] --> the_6_4["the"]
    level_5_3["level"] --> dry_6_5["dry"]
    level_5_3["level"] --> run_6_6["run"]
    at_5_4["at"] --> step_6_7["step"]
    at_5_4["at"] --> by_6_8["by"]
    left_5_5["left"] --> step_6_9["step"]
    N_6_6_1["6"] --> N_7_7_1["7"]
    N_6_6_1["6"] --> State_7_2["State"]
    Walk_6_2["Walk"] --> O_7_3["O"]
    Walk_6_2["Walk"] --> n_7_4["n"]
    through_6_3["through"] --> time_7_5["time"]
    through_6_3["through"] --> and_7_6["and"]
    the_6_4["the"] --> O_7_7["O"]
    the_6_4["the"] --> N_1_7_8["1"]
    dry_6_5["dry"] --> space_7_9["space"]
    N_7_7_1["7"] --> N_8_8_1["8"]
    N_7_7_1["7"] --> Mention_8_2["Mention"]
    State_7_2["State"] --> edge_8_3["edge"]
    State_7_2["State"] --> cases_8_4["cases"]
    O_7_3["O"] --> fewer_8_5["fewer"]
    O_7_3["O"] --> than_8_6["than"]
    n_7_4["n"] --> N_3_8_7["3"]
    n_7_4["n"] --> bars_8_8["bars"]
    time_7_5["time"] --> flat_8_9["flat"]
    time_7_5["time"] --> array_8_10["array"]
    and_7_6["and"] --> single_8_11["single"]
    and_7_6["and"] --> valley_8_12["valley"]

Interview Tips

Interviewers often ask:

What is the water formula for a single bar?
Why does the Two Pointer approach not need both leftMax and rightMax simultaneously?
What is the loop invariant?
How does this differ from Container With Most Water?
Why start with the prefix/suffix approach before the Two Pointer?
What is the space complexity of each approach?
What happens when all bars are the same height?
When would you prefer the stack approach over Two Pointer?
How do you handle integer overflow for very large inputs?
Can this be solved in a single pass from left to right only?

Be prepared to explain why moving the shorter-side pointer is safe before writing code.

Problem	Formula	Goal
Container With Most Water	`min(h[L], h[R]) × width`	Maximize
Trapping Rain Water	`sum of min(leftMax, rightMax) - h[i]`	Sum all

Unit Tests

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class TrappingRainWaterTest {

    final TrappingRainWater solution =
            new TrappingRainWater();

    @Test
    void example1() {
        assertEquals(6,
                solution.trap(
                        new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    @Test
    void example2() {
        assertEquals(9,
                solution.trap(
                        new int[]{4, 2, 0, 3, 2, 5}));
    }

    @Test
    void example3() {
        assertEquals(7,
                solution.trap(
                        new int[]{3, 0, 2, 0, 4}));
    }

    @Test
    void singleBar() {
        assertEquals(0,
                solution.trap(new int[]{5}));
    }

    @Test
    void twoBars() {
        assertEquals(0,
                solution.trap(new int[]{3, 5}));
    }

    @Test
    void flatArray() {
        assertEquals(0,
                solution.trap(new int[]{3, 3, 3, 3}));
    }

    @Test
    void monotonicallyIncreasing() {
        assertEquals(0,
                solution.trap(new int[]{1, 2, 3, 4, 5}));
    }

    @Test
    void monotonicallyDecreasing() {
        assertEquals(0,
                solution.trap(new int[]{5, 4, 3, 2, 1}));
    }

    @Test
    void singleValley() {
        assertEquals(3,
                solution.trap(new int[]{3, 0, 3}));
    }

    @Test
    void asymmetricWalls() {
        assertEquals(1,
                solution.trap(new int[]{1, 0, 5}));
    }

    @Test
    void allZeros() {
        assertEquals(0,
                solution.trap(new int[]{0, 0, 0, 0}));
    }

    @Test
    void nullInputReturnsZero() {
        assertEquals(0,
                solution.trap(null));
    }

}

Summary

Trapping Rain Water is the canonical problem for understanding how two pointers can replace precomputed prefix and suffix arrays. The brute-force O(n²) approach recomputes left and right maximums for every bar. The prefix/suffix approach brings this to O(n) time but requires O(n) space. The Two Pointer approach achieves O(n) time and O(1) space by maintaining running maximums and processing whichever side has the smaller current maximum — because the other side is guaranteed to be at least as tall, making the water contribution exact without needing both maximums simultaneously. Mastering this problem provides the intuition for Trapping Rain Water II, Largest Rectangle in Histogram, and many other bar-based problems.

Key Takeaways

Water above each bar equals max(0, min(leftMax, rightMax) - height[i]).
Brute force is O(n²) — avoid recomputing maximums per bar.
Prefix/suffix arrays give O(n) time but cost O(n) space.
Two Pointer achieves O(n) time and O(1) space with running maximums.
Process the side with the smaller current height — it determines the water level.
Update leftMax or rightMax before computing water — not after.
When height[left] <= height[right], the water at left is exactly leftMax - height[left].
Arrays shorter than 3 trap no water — return 0 early.
Use long for the total when heights or array lengths are very large.
Distinguish this from Container With Most Water — different formula, different goal, different pointer logic.

left	right	h[L]	h[R]	lMax	rMax	water added	total
0	11	0	1	0	0	0	0
1	11	1	1	1	0	0	0
2	11	0	1	1	0	1	1
3	11	2	1	1	1	0	1
3	10	2	2	2	1	0	1
4	10	1	2	2	1	1	2
5	10	0	2	2	1	2	4
6	10	1	2	2	1	1	5
7	10	3	2	2	2	0	5
7	9	3	1	2	2	1	6
7	8	3	2	2	2	0	6

left	right	h[L]	h[R]	lMax	rMax	water added	total
0	11	0	1	0	0	0	0
1	11	1	1	1	0	0	0
2	11	0	1	1	0	1	1
3	11	2	1	1	1	0	1
3	10	2	2	2	1	0	1
4	10	1	2	2	1	1	2
5	10	0	2	2	1	2	4
6	10	1	2	2	1	1	5
7	10	3	2	2	2	0	5
7	9	3	1	2	2	1	6
7	8	3	2	2	2	0	6

left	right	h[L]	h[R]	lMax	rMax	water added	total
0	11	0	1	0	0	0	0
1	11	1	1	1	0	0	0
2	11	0	1	1	0	1	1
3	11	2	1	1	1	0	1
3	10	2	2	2	1	0	1
4	10	1	2	2	1	1	2
5	10	0	2	2	1	2	4
6	10	1	2	2	1	1	5
7	10	3	2	2	2	0	5
7	9	3	1	2	2	1	6
7	8	3	2	2	2	0	6