Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
Contents
- Approach 1 — Prefix/Suffix Max Arrays O(n) space
- Approach 2 — Two Pointers O(1) space
- Complexity Analysis
Prefix/Suffix Max Arrays
Water above position i = min(maxLeft[i], maxRight[i]) - height[i].
Pre-compute the running maximum from the left and from the right.
public int trap(int[] height) {
int n = height.length;
int[] maxLeft = new int[n]; // maxLeft[i] = max height in [0..i]
int[] maxRight = new int[n]; // maxRight[i] = max height in [i..n-1]
maxLeft[0] = height[0];
for (int i = 1; i < n; i++) {
maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
}
maxRight[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxRight[i] = Math.max(maxRight[i + 1], height[i]);
}
int water = 0;
for (int i = 0; i < n; i++) {
water += Math.min(maxLeft[i], maxRight[i]) - height[i];
}
return water;
}
Two Pointers O(1) Space
We can avoid the extra arrays. Water at position i depends on the minimum of the max
from the left and max from the right. We process the side with the smaller max first — that side's water
is already determined.
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] <= height[right]) {
// left side is the limiting factor
if (height[left] >= leftMax) {
leftMax = height[left]; // update max
} else {
water += leftMax - height[left]; // trapped water
}
left++;
} else {
// right side is the limiting factor
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
| Approach | Time | Space |
|---|
| Prefix/Suffix Max | O(n) | O(n) |
| Two Pointers | O(n) | O(1) |