Trapping Rain Water — The Two-Pointer Hard Problem That Tests Real Skill

Problem Statement#

Given an array height[] of non-negative integers representing the elevation of bars of width 1, compute how much rainwater is trapped after it rains.

Constraints:

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

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

Why This Problem Matters#

LeetCode 42 Trapping Rain Water is one of the most-asked Hard problems at Amazon, Google, Microsoft, and Facebook. It tests four skills at once: visualization, the two pointer technique, prefix-max thinking, and constant-extra-space optimization. If you can derive the O(1) space solution on a whiteboard, you have effectively cleared the algorithmic bar for an SDE-2 onsite.

Keywords interviewers expect: two pointer trapping rainwater, prefix max suffix max, monotonic stack rainwater, and O(1) space rainwater.

The Core Insight#

Water trapped above bar i equals min(maxLeft[i], maxRight[i]) - height[i]. The brute force is O(n^2). The optimal observation: if leftMax < rightMax, the water above the left pointer is determined entirely by leftMax (the right side cannot leak). That lets us safely advance the smaller-side pointer and accumulate water in one pass.

Visual Dry Run#

Walking the two-pointer solution on [0,1,0,2,1,0,1,3,2,1,2,1]:

Total trapped water: 6.

Solution (Optimal Two Pointer)#

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

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

Time: O(n) — each index is visited once. Space: O(1) — only four scalars.

Alternate Approach: Monotonic Stack#

A monotonic decreasing stack pops bars when a taller one arrives, computing horizontal slabs of water. Also O(n) time but O(n) space.

class Solution:
    def trap(self, height: list[int]) -> int:
        stack, water = [], 0
        for i, h in enumerate(height):
            while stack and height[stack[-1]] < h:
                bottom = stack.pop()
                if not stack: break
                left = stack[-1]
                width = i - left - 1
                bounded = min(height[left], h) - height[bottom]
                water += width * bounded
            stack.append(i)
        return water

Common Mistakes#

• Updating leftMax/rightMax after adding water — must update first when height[l] >= leftMax.
• Using <= instead of < and double-counting the equal-height case.
• Forgetting to handle empty arrays or arrays of length 1 or 2 (trivially 0).
• Trying to use a fixed-size sliding window — water depends on global maxima, not local windows.
• Stack solution: forgetting to break when stack empties after popping.

Interview Tips#

• Open with the brute force using prefix_max and suffix_max arrays so the interviewer sees you understand the math. Then optimize to two pointers.
• Verbalize the invariant: "Whichever side has the smaller current bar, that side's accumulated max is the binding constraint, so I can safely process it."
• Sketch the histogram on the whiteboard — visual proof seals the deal.
• Mention the alternative monotonic-stack solution as a follow-up.

Follow-up Questions#

• Trapping Rain Water II (LeetCode 407): 2D grid version — needs a min heap with BFS from the boundary inward.
• Container With Most Water (LeetCode 11): simpler cousin — only looks at the two outer bars, not interior trapping.
• Largest Rectangle in Histogram (LeetCode 84): related monotonic stack problem.
• What if heights are streaming? Maintain prefix and suffix max via two passes; cannot do two-pointer streaming.
• What if heights can be negative? Adjust the formula by shifting all values up by min(height).

Key Takeaways#

• Trapping Rain Water is the canonical hard interview problem for the two pointer technique with running maxima.
• The optimal solution runs in O(n) time and O(1) extra space — the smaller bar always determines the binding side.
• Remember the rule: if height[l] < height[r], advance left; otherwise advance right.
• A monotonic stack solves the same problem in O(n)/O(n) and is a useful cousin for Largest Rectangle in Histogram.
• For 2D variants, the boundary-min-heap BFS pattern generalizes the same "smallest wall determines water" intuition.
• Always derive the brute force first, then optimize — interviewers reward the journey, not just the final code.
• This problem and Sliding Window Maximum together teach the two highest-yield monotonic patterns in DSA interviews.