Trapping Rain Water
A 2D platform game builds its terrain from columns of blocks. Column i is height[i] blocks tall, every column is exactly one block wide, and the columns stand side by side with no gaps.
When it rains, water settles in the dips between taller columns, while any water that reaches the left or right edge of the level drains away. Return how many blocks of water the terrain holds once the rain stops.
Input: height = [4,1,3,0,2] Output: 4
Explanation: Two blocks of water sit above column 1 and two above column 3. The water over column 3 is capped by the last column, which is only 2 tall.
Input: height = [5,2,2,5] Output: 6
Explanation: The flat basin fills up to height 5: 3 + 3 = 6 blocks.
Input: height = [3,2,1] Output: 0
Explanation: The terrain only slopes down, so all the rain drains off the right edge.
Constraints
- The terrain has between 1 and 20,000 columns.
- Each column is between 0 and 10^5 blocks tall.
💡 Hint 1
The water above bar i is min(tallest bar to its left, tallest bar to its right) - height[i] (counting bar i itself on both sides).
💡 Hint 2
Precomputing the left and right maxima in two arrays gives an O(n) time, O(n) space solution.
💡 Hint 3
For O(1) space, use two pointers. Whichever side has the smaller maximum so far is the bottleneck, so the water over that pointer is already known.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
The water above bar i is min(maxLeft, maxRight) - height[i]. Use two pointers lo and hi at the ends, plus the tallest bar seen from each side, leftMax and rightMax. If leftMax <= rightMax, then the real right maximum for lo is at least rightMax, so the water over lo is exactly leftMax - height[lo]: add it and move lo right. Otherwise the same argument settles hi from the right. Each step fixes one bar, so a single pass with O(1) extra space suffices.
function trap(height) {
let lo = 0;
let hi = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (lo <= hi) {
leftMax = Math.max(leftMax, height[lo]);
rightMax = Math.max(rightMax, height[hi]);
if (leftMax <= rightMax) {
water += leftMax - height[lo];
lo++;
} else {
water += rightMax - height[hi];
hi--;
}
}
return water;
}class Solution {
public int trap(int[] height) {
int lo = 0, hi = height.length - 1, leftMax = 0, rightMax = 0, water = 0;
while (lo <= hi) {
leftMax = Math.max(leftMax, height[lo]);
rightMax = Math.max(rightMax, height[hi]);
if (leftMax <= rightMax) {
water += leftMax - height[lo];
lo++;
} else {
water += rightMax - height[hi];
hi--;
}
}
return water;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} height
* @return {number}
*/
function trap(height) {
}Run your code to see results here.