Trapping Rain Water

How it works

Water at any position depends on the shorter wall between the left and right sides. So if the left wall is shorter, the right wall can't help us—water is limited by the left side. That means we safely move the left pointer inward and calculate how much water can be trapped there. Similarly, if the right wall is shorter, we move the right pointer left.

As we move the pointers, we keep track of the highest wall seen so far on each side (leftMax and rightMax). The water at each position is simply:

max wall on that side – height at that position

Steps

1. Set two pointers:
   • l at the start
   • r at the end Track leftMax and rightMax as the tallest walls seen.
2. While l < r:
   • If leftMax < rightMax:
     • Move l right.
     • Update leftMax.
     • Add leftMax - height[l] to the result.
   • Else:
     • Move r left.
     • Update rightMax.
     • Add rightMax - height[r] to the result.
3. Return the total trapped water.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Calculating Water at Boundary Bars

The leftmost and rightmost bars can never hold water above them since there's no wall on one side to contain it. Including them in water calculations gives wrong results.

Using Current Bar Height Instead of Max Heights

Water at each position depends on the minimum of the maximum heights to its left and right, minus the current height. Using the current bar's height in the max comparison instead of tracking running maximums is incorrect.

Negative Water Values

When the current bar is taller than the limiting wall, the water calculation yields a negative value. This happens at peaks and should contribute zero water, not negative.

Wrong Pointer Movement in Two Pointers

In the two-pointer approach, always move the pointer on the side with the smaller max height. Moving the wrong pointer breaks the invariant that the smaller side determines the water level.

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

        int l = 0, r = height.size() - 1;
        int leftMax = height[l], rightMax = height[r];
        int res = 0;
        while (l < r) {
            if (leftMax < rightMax) {
                l++;
                leftMax = max(leftMax, height[l]);
                res += leftMax - height[l];
            } else {
                r--;
                rightMax = max(rightMax, height[r]);
                res += rightMax - height[r];
            }
        }
        return res;
    }
};