Problem
Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.
Example
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6Solution
Two pointers from both ends. Track max heights seen from each side. Water at position = min(maxL, maxR) – height[i].
def trap(height):
l, r = 0, len(height) - 1
max_l = max_r = water = 0
while l < r:
if height[l] < height[r]:
max_l = max(max_l, height[l])
water += max_l - height[l]
l += 1
else:
max_r = max(max_r, height[r])
water += max_r - height[r]
r -= 1
return waterfunction trap(height) {
let l = 0, r = height.length - 1;
let maxL = 0, maxR = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
maxL = Math.max(maxL, height[l]);
water += maxL - height[l];
l++;
} else {
maxR = Math.max(maxR, height[r]);
water += maxR - height[r];
r--;
}
}
return water;
}int trap(vector<int>& height) {
int l = 0, r = height.size() - 1, maxL = 0, maxR = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
maxL = max(maxL, height[l]);
water += maxL - height[l];
l++;
} else {
maxR = max(maxR, height[r]);
water += maxR - height[r];
r--;
}
}
return water;
}public int trap(int[] height) {
int l = 0, r = height.length - 1, maxL = 0, maxR = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
maxL = Math.max(maxL, height[l]);
water += maxL - height[l];
l++;
} else {
maxR = Math.max(maxR, height[r]);
water += maxR - height[r];
r--;
}
}
return water;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
The water trapped at any cell depends on the smaller of the max heights to its left and right. Two pointers let us know which side’s max is the constraining one.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?