Trapping Rain Water
Hard · rating 2000 · Two Pointers
The first line has n. The second line has n non-negative integers, an elevation map (each bar width 1). Print the total units of water trapped after it rains.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Water above a bar is bounded by the tallest wall to its left and to its right — specifically min(leftMax, rightMax) - height. Two pointers compute this in one pass: advance from whichever side has the smaller running max, because that side is the true bottleneck for the current bar.
Why the smaller side is safe
If leftMax < rightMax, the left bar's water depends only on leftMax (some wall at least that tall exists on the right), so it can be finalized immediately.
i, j = 0, n - 1; lm = rm = res = 0
while i < j:
if h[i] < h[j]:
lm = max(lm, h[i]); res += lm - h[i]; i += 1
else:
rm = max(rm, h[j]); res += rm - h[j]; j -= 1Complexity
Time: O(n). Space: O(1).
Related problems
- Container With Most Water — Medium
- Minimum Size Subarray Sum — Medium
- Subarrays With Product Below K — Medium
- Subarray With Target Sum — Medium
- Sort Colors — Medium
- Two Sum (Sorted) — Medium