Trapping Rain Water — Three Approaches Every Senior Engineer Must Know

Problem Statement#

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water can be trapped after raining.

Constraints:

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

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

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

Why This Problem Matters#

Trapping Rain Water is one of the most iconic hard problems in FAANG interviews. Google and Meta ask it in onsite rounds specifically because it has three distinct solutions at different complexity levels, and interviewers use those three approaches to test progressively deeper understanding. Knowing only one approach is a yellow flag. Knowing all three — and explaining the trade-offs — is a green flag for senior-level positions.

The three approaches are:

1. Prefix/suffix max arrays — O(n) time, O(n) space. Clean and easy to understand.
2. Monotonic stack — O(n) time, O(n) space. Generalizes to other histogram problems.
3. Two pointers — O(n) time, O(1) space. The optimal interview solution.

The Core Insight#

The fundamental insight: water level at position i equals min(max_left[i], max_right[i]) - height[i], where max_left[i] is the tallest bar at or to the left of i, and max_right[i] is the tallest bar at or to the right of i. Water fills up to the minimum of the two walls, minus the actual height.

For the two-pointer O(1) space approach: you do not need both max values simultaneously. You only need the smaller one, because the smaller wall determines the water level.

• If max_left <= max_right: the left side is the bottleneck. Water at left = max_left - height[left]. Advance left.
• If max_right < max_left: symmetrically advance right.

Visual Dry Run#

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

Two-pointer trace (partial):

Solution (Optimal)#

class Solution:
    def trap(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        max_left = max_right = 0
        water = 0
 
        while left < right:
            if height[left] <= height[right]:
                if height[left] >= max_left:
                    max_left = height[left]
                else:
                    water += max_left - height[left]
                left += 1
            else:
                if height[right] >= max_right:
                    max_right = height[right]
                else:
                    water += max_right - height[right]
                right -= 1
 
        return water

var trap = function(height) {
    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;
};

Time: O(n) — single pass with two pointers Space: O(1) — only four integer variables

Common Mistakes#

• Not understanding why the two-pointer decision works — when max_left <= max_right, the right side is guaranteed to be at least max_right, so the left wall is the bottleneck and we can safely compute water at left without knowing the exact right boundary
• Off-by-one in max updates — update max_left BEFORE computing water at the current position; the conditional if height[left] >= max_left handles this naturally
• Confusing the monotonic stack approach (uses a decreasing stack for rain water) with the histogram approach (uses an increasing stack for rectangle area) — getting the direction wrong produces wrong answers
• Adding negative water — always use max(0, ...) or the conditional structure above to avoid subtracting a taller bar from a shorter wall

Interview Tips#

• Present all three approaches upfront: "There are three ways. The prefix/suffix array approach is most readable. The monotonic stack approach generalizes to histograms. The two-pointer approach is O(1) space — I will implement that one unless you prefer another."
• When explaining two pointers, use the analogy: "Think of pouring water from both ends. At each step, I process whichever side has a shorter wall, because that side is the current bottleneck."
• Prepare to explain why moving the shorter side is correct: "When max_left <= max_right, the right wall is guaranteed to be at least max_right, which is already at least as tall as max_left. So the left wall is the binding constraint and we can compute water at left safely."

Follow-up Questions#

• What if the elevation map is 2D (LC 407 Trapping Rain Water II)? Use a min-heap seeded with all border cells; BFS outward from smallest border cell; water trapped = max(0, min_wall - height[cell]). O(mnlog(m*n)).
• How does this relate to Container With Most Water (LC 11)? Same two-pointer logic: move the shorter bar inward. Area = min(height[l], height[r]) * (r - l).
• How does this relate to Largest Rectangle in Histogram? Rain water uses a decreasing stack (find water from below); histogram uses an increasing stack (find rectangle area from above). Same structure, opposite direction.

Key Takeaways#

• Water at each position equals min(max_left, max_right) - height[i] — this formula is the foundation of all three approaches.
• The two-pointer approach achieves O(1) space by processing whichever side has a smaller max wall, since that side is the current bottleneck.
• When max_left <= max_right, the right side is guaranteed to be at least max_right >= max_left, so computing water at left is safe.
• Present all three approaches (prefix arrays, monotonic stack, two pointers) at the start of the interview — this signals depth and gives the interviewer a choice.
• The monotonic stack for rain water uses a decreasing stack; the histogram uses an increasing stack — opposite directions for related problems.
• Always update the running max before computing water to avoid counting the current bar as its own wall.
• This problem is a senior-level filter at Google and Meta because the O(1) space invariant explanation distinguishes memorized solutions from genuine understanding.