LeetCode 42 ·
Hard
Trapping Rain Water
Given bar heights, compute how much rain water is trapped between them.
Try it
Step through the core mechanic. The simulator below runs the two pointers shape this problem is built on.
Interactive · Two-pointers walkthrough Two Sum II (sorted): find a pair that sums to target.
0
1
L
1
2
2
3
3
5
4
8
5
11
6
14
7
17
8
21
R
start: a[L] + a[R] = 22
Why two pointers works.
Because the array is sorted, every position pair (L, R) is uniquely
determined by its sum's relation to the target. If
sum < target,
moving L right is the only way to grow the sum without moving R; if sum > target,
moving R left is the only way to shrink it. The pointers never need to revisit —
that's why it's O(n) instead of the obvious O(n²).The approach
Water over a bar is min(maxLeft, maxRight) − height. Two pointers carry running left/right maxima; process the side with the smaller max, because that side's bound is already known.
| Aspect | Value |
|---|---|
| Pattern | Two pointers |
| Recognise it by | Water trapped above an elevation map. |
| Time complexity | O(n) |
| Space complexity | O(1) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.