#42 - Trapping Rain Water
HardArray / String
Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining.
| Input | Output |
|---|---|
height = [0,1,0,2,1,0,1,3,2,1,2,1] | 6 |
height = [4,2,0,3,2,5] | 9 |
Solution Space
ts
/**
* Computes the total units of water trapped between bars.
*
* Water at position i = min(leftMax, rightMax) - height[i].
* Two pointers converge inward, always processing the lower side
* because that side's max is the true bottleneck.
*
* @param height Array of non-negative bar heights
* @returns Total trapped water units
*/
export function trap(height: number[]): number {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Approach: two-pointer – maintain `leftMax`/`rightMax` while converging pointers inward; always process the side with the smaller max, since that max is the bottleneck for water at that position.
Time: O(n) – single pass with two converging pointers.
Space: O(1) – only a few tracking variables.
Alternative approaches:
| Approach | Idea | Time | Space |
|---|---|---|---|
| Prefix-max arrays | Pre-compute leftMax[i] and rightMax[i], then water += min(leftMax[i], rightMax[i]) - height[i]. | O(n) | O(n) |
| Monotonic stack | Maintain a decreasing stack; on a taller bar, pop and compute bounded water. | O(n) | O(n) |
Why two-pointer is preferred:
- Same O(n) time as prefix-max arrays but uses O(1) space instead of O(n).
- Conceptually simpler than the monotonic-stack approach once the invariant ("process the lower side") is understood.