Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Trapping Rain Water (LC 42)

Problem Statement

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

Example 1:

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Example 2:

Input:  height = [4,2,0,3,2,5]
Output: 9

Constraints:

• 1 <= height.length <= 2 * 10^4
• 0 <= height[i] <= 10^5

Difficulty: Hard

---

Pattern Recognition

• Input structure: a 1D array of bar heights.
• What are we computing? total water volume across all indices.
• Pattern: two pointers with running max (optimal) or monotonic stack.
• Why: water above index i equals min(maxLeft, maxRight) - height[i]. Once you see that, the game is how to compute those two maxes efficiently.

---

Approach

Brute Force

For each i, scan left for maxLeft, right for maxRight, add min(...) - height[i]. O(n^2). TLE.

Better — Precompute Prefix/Suffix Max

Build maxLeft[i] and maxRight[i] in two passes, then sum. O(n) time, O(n) space. Clean, obvious, easy to write during an interview.

Optimal — Two Pointers, O(1) Space

Key Insight: If height[left] < height[right], whatever is to the right of left contains some bar at least as tall as height[left]. So the water at left is fully determined by maxLeftSoFar. Symmetric on the other side.

left = 0, right = n - 1
maxLeft = 0, maxRight = 0
water = 0
while left < right:
    if height[left] < height[right]:
        if height[left] >= maxLeft: maxLeft = height[left]
        else: water += maxLeft - height[left]
        left++
    else:
        if height[right] >= maxRight: maxRight = height[right]
        else: water += maxRight - height[right]
        right--

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

Alternative — Monotonic Stack

Maintain a decreasing stack of indices. When height[i] exceeds the top, pop and fill a "U-shape" region. Adds water layer-by-layer. Same O(n), different mental model — useful for building intuition toward Largest Rectangle in Histogram (LC 84).

---

Walkthrough

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

Initial: left=0, right=11, maxLeft=0, maxRight=0, water=0.

l	r	h[l]	h[r]	side	action	maxL	maxR	water
0	11	0	1	left	h[l] ≥ maxL, update	0	0	0
1	11	1	1	right	h[r] ≥ maxR, update	0	1	0
1	10	1	2	left	h[l] ≥ maxL, update	1	1	0
2	10	0	2	left	add maxL - 0 = 1	1	1	1
3	10	2	2	right	h[r] ≥ maxR, update	1	2	1
3	9	2	1	right	add maxR - 1 = 1	1	2	2
3	8	2	2	right	h[r] ≥ maxR, update	1	2	2
3	7	2	3	left	h[l] ≥ maxL, update	2	2	2
4	7	1	3	left	add 2 - 1 = 1	2	2	3
5	7	0	3	left	add 2 - 0 = 2	2	2	5
6	7	1	3	left	add 2 - 1 = 1	2	2	6
7	7	stop

Answer: 6.

---

Implementation

TypeScript

function trap(height: number[]): number {
    let left = 0, right = height.length - 1;
    let maxLeft = 0, maxRight = 0;
    let water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= maxLeft) maxLeft = height[left];
            else water += maxLeft - height[left];
            left++;
        } else {
            if (height[right] >= maxRight) maxRight = height[right];
            else water += maxRight - height[right];
            right--;
        }
    }
    return water;
}

C++

int trap(vector<int>& height) {
    int left = 0, right = (int)height.size() - 1;
    int maxLeft = 0, maxRight = 0;
    int water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= maxLeft) maxLeft = height[left];
            else water += maxLeft - height[left];
            left++;
        } else {
            if (height[right] >= maxRight) maxRight = height[right];
            else water += maxRight - height[right];
            right--;
        }
    }
    return water;
}

Watch out:

1. Updating maxLeft before you compute the contribution causes double counting on flat stretches — update only when height[left] >= maxLeft.
2. Using <= instead of < in the pointer comparison affects edge behavior at equal heights — both versions give correct totals but the walkthrough changes. Pick one and be consistent.
3. For the stack method, forgetting to multiply width by the min height minus the bottom bar gives wrong area totals.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(1)
Prefix/Suffix Max	O(n)	O(n)
Two Pointers	O(n)	O(1)
Monotonic Stack	O(n)	O(n)

Bottleneck: O(n) is optimal since every bar contributes to the total. Two pointers wins on space.

---

Edge Cases

1. Length < 3 — no water can be trapped. Loop condition handles it.
2. Monotonically increasing — no trapping; pointers always move from the shorter side, no accumulation.
3. Monotonically decreasing — same; no valleys.
4. All bars equal — zero water. Both branches hit the "update max" path.
5. Very tall single bar surrounded by zeros — water equals (n-1) * 0 at edges but the bar itself traps nothing outside its own width.
6. Zero heights — fine; min - 0 contributes up to min per cell.

---

Related Problems

• LC 11 — Container With Most Water — Two pointers on heights; max area instead of trapped water.
• LC 407 — Trapping Rain Water II — 2D version with a min-heap sweep. Great follow-up.
• LC 84 — Largest Rectangle in Histogram — Same monotonic-stack idea as the alternative approach.
• LC 238 — Product of Array Except Self — Another prefix/suffix precompute pattern, different aggregation.

---

What Is Expected at Each Level

Junior: Get to the prefix/suffix O(n) space solution and state complexity. The two-pointer version may need a nudge.

Mid-level: Two-pointer O(1) space on first try, confident explanation of the invariant, correct handling of the equal-height case.

Senior (L4 target): Present two-pointer and monotonic-stack approaches, contrast them, mention the 2D extension (LC 407, heap-based), and articulate the invariant — "the shorter side is bottlenecked" — in a way that transfers to Container With Most Water.