# Trapping Rain Water

- **Canonical ID**: `trapping-rain-water`
- **Canonical URL**: https://dsacheatsheet.com/problems/trapping-rain-water
- **Difficulty**: hard
- **Patterns**: Two Pointers
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/trapping-rain-water/

## 1. Core Invariant / The Trick

Water above bar `i` equals `min(maxLeft, maxRight) - height[i]`. Using two pointers maintaining `leftMax` and `rightMax`, whenever `leftMax <= rightMax`, the right side is guaranteed >= `leftMax`, so water at `l` is finalized cleanly in O(1) space!

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Because `leftMax` and `rightMax` are non-decreasing prefixes/suffixes, the smaller side always safely determines `min(maxLeft, maxRight)` at its frontier.

## 3. Minimal Idiomatic Code

### Python
```python
def trap(height: list[int]) -> int:
    l, r = 0, len(height) - 1
    l_max = r_max = 0
    water = 0
    while l < r:
        if height[l] < height[r]:
            l_max = max(l_max, height[l])
            water += l_max - height[l]
            l += 1
        else:
            r_max = max(r_max, height[r])
            water += r_max - height[r]
            r -= 1
    return water
```

### TypeScript
```typescript
export function trap(height: number[]): number {
  let l = 0, r = height.length - 1, lMax = 0, rMax = 0, water = 0;
  while (l < r) {
    if (height[l] < height[r]) {
      lMax = Math.max(lMax, height[l]);
      water += lMax - height[l++];
    } else {
      rMax = Math.max(rMax, height[r]);
      water += rMax - height[r--];
    }
  }
  return water;
}
```

### C++
```cpp
int trap(vector<int>& h) {
    int l = 0, r = h.size() - 1, lMax = 0, rMax = 0, ans = 0;
    while (l < r) {
        if (h[l] < h[r]) { lMax = max(lMax, h[l]); ans += lMax - h[l++]; }
        else { rMax = max(rMax, h[r]); ans += rMax - h[r--]; }
    }
    return ans;
}
```

### Java
```java
int trap(int[] h) {
    int l = 0, r = h.length - 1, lMax = 0, rMax = 0, ans = 0;
    while (l < r) {
        if (h[l] < h[r]) { lMax = Math.max(lMax, h[l]); ans += lMax - h[l++]; }
        else { rMax = Math.max(rMax, h[r]); ans += rMax - h[r--]; }
    }
    return ans;
}
```

### Go
```go
func trap(h []int) int {
    l, r, lMax, rMax, ans := 0, len(h)-1, 0, 0, 0
    for l < r {
        if h[l] < h[r] {
            lMax = max(lMax, h[l]); ans += lMax - h[l]; l++
        } else {
            rMax = max(rMax, h[r]); ans += rMax - h[r]; r--
        }
    }
    return ans
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Updating `leftMax` before computing `leftMax - height[l]` ensures non-negative water clamped naturally at 0.

### Follow-ups
- 2D Trapping Rain Water II requires a min-heap prioritizing the lowest perimeter boundary.