Trapping Rain Water — Two-Pointer O(n) O(1) [LC 42]

Problem Statement#

Given 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.

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#

LeetCode 42 is one of the most famous hard problems in FAANG interviews — asked at Amazon, Google, Microsoft, and Meta with very high frequency. It tests multiple skills simultaneously: understanding the water-level formula, reasoning about left/right maxima, and optimizing from O(n) space to O(1) space using two pointers.

The two-pointer solution is an elegant example of "defer the decision to whichever side is more constrained." This principle — moving the pointer with less information inward — appears in Container With Most Water (LC 11) and is a key pattern in two-pointer interview technique.

The Core Insight#

Water at position i = min(left_max[i], right_max[i]) - height[i]

This is the formula: water trapped above position i is the minimum of the maximum heights to the left and right of it, minus the height at i. If this is negative, no water is trapped (the height exceeds the min boundary).

Two-pointer O(1) space insight: Instead of precomputing left_max and right_max arrays, use two pointers lo and hi from each end:

• Track left_max (max seen from the left) and right_max (max seen from right)
• The pointer with the smaller max is the "bottleneck" — water at that side is determined by its own max (regardless of the unknown other side)
• Move the smaller-max pointer inward, compute water, update its max

Why this works: If left_max < right_max, then even though we don't know the exact right wall, we know it's at least right_max. The water at lo is left_max - height[lo] — the right side can't limit us below left_max since it's already higher.

Visual Dry Run#

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

Simpler trace:

• lo=0 (h=4), hi=5 (h=5): left_max=4, right_max=5. left_max < right_max → process lo. water += max(0, 4-4)=0. lo=1.
• lo=1 (h=2), hi=5: left_max=4, right_max=5. process lo. water += max(0, 4-2)=2. lo=2.
• lo=2 (h=0), hi=5: left_max=4, right_max=5. process lo. water += max(0, 4-0)=4. lo=3.
• lo=3 (h=3), hi=5: left_max=4, right_max=5. process lo. water += max(0, 4-3)=1. lo=4.
• lo=4 (h=2), hi=5: left_max=4, right_max=5. process lo. water += max(0, 4-2)=2. lo=5.
• lo=hi=5: done.

Total: 0+2+4+1+2=9. Correct!

Solution (Optimal)#

class Solution:
    def trap(self, height):
        lo, hi = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while lo < hi:
            if height[lo] < height[hi]:
                if height[lo] >= left_max:
                    left_max = height[lo]
                else:
                    water += left_max - height[lo]
                lo += 1
            else:
                if height[hi] >= right_max:
                    right_max = height[hi]
                else:
                    water += right_max - height[hi]
                hi -= 1
        return water

var trap = function(height) {
    let lo = 0, hi = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let water = 0;
    while (lo < hi) {
        if (height[lo] < height[hi]) {
            if (height[lo] >= leftMax) leftMax = height[lo];
            else water += leftMax - height[lo];
            lo++;
        } else {
            if (height[hi] >= rightMax) rightMax = height[hi];
            else water += rightMax - height[hi];
            hi--;
        }
    }
    return water;
};

Time: O(n) — each element processed exactly once Space: O(1) — four scalar variables only

Common Mistakes#

• Using O(n) space precomputed arrays — works correctly but wastes space (precompute left_max and right_max arrays first)
• Computing water as height[i] - min(left, right) instead of min(left, right) - height[i] — inverted formula
• Moving both pointers when heights are equal — only move one (here we move hi, but either works)
• Not updating left_max and right_max before computing water — max must include the current position
• Forgetting the max(0, ...) guard — when height exceeds the min boundary, no water is trapped (the two-pointer version handles this implicitly)

Interview Tips#

• Start with the O(n) space approach using precomputed arrays — easier to explain, then optimize
• State the formula clearly: "water at i = min(left_max, right_max) - height[i]"
• Explain the two-pointer insight: "if left_max < right_max, the right side is at least right_max — the left side is the bottleneck"
• Draw the histogram and physically show where water pools for the example
• Mention alternative: monotonic stack approach (O(n) time, O(n) space) if asked for multiple solutions

Follow-up Questions#

• What is the O(n) space approach? (Precompute left_max[i] and right_max[i] arrays, then sum max(0, min(left_max[i], right_max[i]) - height[i]))
• What is the monotonic stack approach? (Process in one pass using a stack to track decreasing heights; compute water as bars are popped)
• How does this relate to Container With Most Water (LC 11)? (Both use two pointers meeting in the middle; both move the smaller-side pointer — same underlying principle)
• What if the elevation map is 2D? (LC 407 — Trapping Rain Water II; uses a min-heap BFS from the boundary inward)
• Can you find the total water if the array represents a histogram of arbitrary width bars? (Multiply each water unit by the bar width — otherwise same approach)

Key Takeaways#

• LeetCode 42 is asked at Amazon, Google, Microsoft, and Meta — one of the highest-frequency hard problems
• Formula: water at position i = min(left_max, right_max) - height[i]
• Two-pointer insight: move the pointer with the smaller max inward — that side is the bottleneck, its max fully determines water
• Time O(n), Space O(1) — each element processed exactly once with four scalar variables
• O(n) space approach (precompute left_max and right_max arrays) is easier to explain as a first solution
• The "move smaller-side pointer" principle also solves Container With Most Water (LC 11)
• Understanding the water formula first, then deriving the two-pointer optimization, is the strongest interview narrative