Trapping Rain Water

Concept

LeetCode #42.
Problem: 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.

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

This is universally considered one of the hardest “Hard” problems on LeetCode to derive from scratch, but one of the easiest to memorize once you understand the core physical logic.

The Physics of Water

Water is lazy. It flows downhill.
If you pour water onto a specific coordinate (let’s say index i), how high will the water perfectly pool at that exact coordinate?

The water level at index i is strictly defined by the Shortest of the two tallest walls on its Left and Right.
If the absolute tallest wall anywhere to its Left is 4, and the absolute tallest wall anywhere to its Right is 2, the water cannot pool higher than 2. If it tries to reach 3, it will spill over the Right wall!

The Master Formula:
Water at index i = Math.min(MaxLeftWall, MaxRightWall) - height[i]
(If the formula results in a negative number, it means the block of dirt is higher than the walls, so it holds 0 water).

The Dynamic Programming Strategy ($O(N)$ Space)

If we know the Master Formula, how do we efficiently find the MaxLeftWall and MaxRightWall for every single index?
We pre-calculate them!

1. Create an array maxLeft. Iterate left-to-right, storing the highest wall seen so far.
2. Create an array maxRight. Iterate right-to-left, storing the highest wall seen so far.
3. Loop through the original array one final time, applying the Master Formula instantly!

The Two Pointers Masterpiece ($O(1)$ Space)

We can completely eliminate the two DP arrays. We can calculate the water dynamically using Two Pointers.

1. Place left at 0, and right at the end.
2. Track leftMax (starts at 0) and rightMax (starts at 0).
3. The Trick: Compare height[left] and height[right]. Whichever pointer is physically standing on the SMALLER block of dirt is the one that moves!
4. Why? Because water is bottlenecked by the smaller wall! If height[left] < height[right], we confidently know that the Left side is the bottleneck. We don’t even care what exists in the middle of the array! The right side has a massive wall protecting us.
5. If height[left] < height[right]:
   • Is height[left] larger than leftMax? Yes! Update leftMax! (We climbed a new hill, no water holds here).
   • Is it smaller? Yes! Water pools here! Calculate: leftMax - height[left]. Add to total.
   • Move left forward.

Implementation (Two Pointers)

// Time Complexity: O(N) (One pass)
// Space Complexity: O(1) (Pure perfection)

function trap(height: number[]): number {
    if (height.length === 0) return 0;

    let left = 0;
    let right = height.length - 1;

    let leftMax = 0;
    let rightMax = 0;
    
    let totalWater = 0;

    // The pointers walk toward each other until they meet
    while (left < right) {
        
        // Which side is the bottleneck?
        if (height[left] < height[right]) {
            
            // The Left side is smaller! Process the Left pointer.
            if (height[left] >= leftMax) {
                // We climbed a new peak! Update the boundary.
                leftMax = height[left];
            } else {
                // We are in a valley! Trap the water!
                totalWater += leftMax - height[left];
            }
            
            left++; // Move forward
            
        } else {
            
            // The Right side is smaller (or equal)! Process the Right pointer.
            if (height[right] >= rightMax) {
                // We climbed a new peak! Update the boundary.
                rightMax = height[right];
            } else {
                // We are in a valley! Trap the water!
                totalWater += rightMax - height[right];
            }
            
            right--; // Move backward
        }
    }

    return totalWater;
}

Interview Questions

Q: A developer tries to solve this using a Monotonic Stack. Is that valid?
A: Yes! The Monotonic Decreasing Stack is a brilliant and perfectly valid $O(N)$ solution. The stack stores the indices of the walls. When you find a block of dirt that is taller than the top of the stack, it means you found the “Right Boundary” of a valley! You pop the stack (which is the bottom of the valley), and calculate the bounded width and height. It is highly complex to write, making the Two Pointers approach preferred for interviews, but the Stack approach is a legendary flex.

Q: In the Two Pointers approach, how can we safely calculate leftMax - height[left] without knowing the absolute maximum peak in the entire array?
A: Because we ONLY move the left pointer if height[left] < height[right].
If we move the left pointer, the right pointer is standing like an unmoving titan on the other side of the map, mathematically guaranteeing that the Right boundary is at least as tall as our left pointer. We don’t need to know the absolute maximum peak; we just need to know that a wall exists somewhere on the right that is taller than our current leftMax!