Trapping Rain Water
A row of bars stands side by side, each one unit wide: height[i] is the height of bar i. Rain collects in the dips between bars. Water stays above a bar only if a taller bar stands somewhere to its left and somewhere to its right; past the first and the last bar it runs off. Return the total units of water the row holds.
Function
- heightinteger-array
- the height of each bar, from left to right
- Returnsinteger
- the total units of trapped water
Constraints
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Every bar is one unit wide, and water does not stay past the first or the last bar.
Examples
- Input
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Output
- 7
- Explanation
- Between the 3 and the 5 the level is 3: 2 units over the 1, 3 over the 0, 1 over the 2. The later 1 sits between the 5 and a 2, so it holds 1. That makes 7.
- Input
- height = [4, 1, 3, 0, 5]
- Output
- 8
- Explanation
- The lower wall is the 4, so the dip fills to level 4: 3 units over the 1, 1 over the 3, 4 over the 0, which makes 8. Water spills over the 4 before the 5 matters.
- Input
- height = [1, 2, 4, 2, 1]
- Output
- 0
- Explanation
- The bars climb to 4 and fall again. Every bar has a side with nothing taller beyond it, so the water runs off and the answer is 0.
Follow-up
Suppose the bars form a 2D grid of heights and water can escape in all four directions. How would you count the trapped water then?
Hints
Open them one at a time. Each one gives away a little more.
Forget the whole row and look at one bar. How high can the water stand above bar
i, and which bars decide that height?The water level above bar
iis the smaller of two numbers: the tallest bar from the start up toi, and the tallest bar fromito the end. Bariholds that level minus its own height. Both running maximums can be built in one pass from each end.You only need the smaller of the two maximums. Put one pointer at each end and keep the tallest bar each pointer has passed. Whichever pointer stands on the lower bar has its level settled by its own running maximum: add that water and move that pointer inward. Stop when the pointers meet.
Solution
The water above a bar depends on bars that can be far away on both sides. Its level is the smaller of the tallest bar on its left and the tallest bar on its right, and the bar holds that level minus its own height. The approaches differ only in how they find those two maximums.
Scan both sides from every bar
Correct, but does not finish on the largest tests
Intuition
For each bar i, scan from 0 to i for the tallest bar on the left and from i to the end for the tallest on the right, then add min(leftMax, rightMax) - height[i]. Including bar i in both scans keeps the amount from going negative and gives the end bars 0.
Every bar reads the whole row: n = 2 × 10^4 means 4 × 10^8 reads, most repeating the scan of the bar before.
Algorithm
- Set
waterto 0. - For each index
i, scan from 0 toiforleftMax. - Scan from
ito the last index forrightMax. - Add
min(leftMax, rightMax) - height[i]towater. - Return
water.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return waterPrecompute the tallest bar on each side
Intuition
The tallest bar from 0 to i is the larger of the tallest bar from 0 to i-1 and height[i]. So one pass from the left fills leftMax, each entry built from the one before, and one pass from the right fills rightMax. A third pass applies the formula.
For [0, 3, 1, 0, 2, 5, 1, 2] the levels min(leftMax[i], rightMax[i]) are [0, 3, 3, 3, 3, 5, 2, 2]. Minus the heights that is [0, 0, 2, 3, 1, 0, 1, 0], which sums to 7. The time is O(n), at the price of two arrays of n numbers.
Algorithm
- Fill
leftMaxfrom left to right:leftMax[0] = height[0], thenleftMax[i] = max(leftMax[i-1], height[i]). - Fill
rightMaxfrom right to left:rightMax[n-1] = height[n-1], thenrightMax[i] = max(rightMax[i+1], height[i]). - For every index add
min(leftMax[i], rightMax[i]) - height[i]to the total. - Return the total.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterTwo pointers that move the lower side
Intuition
The formula needs only the smaller wall, and two pointers can prove which one that is. Start left at 0 and right at the last index, track leftMax and rightMax, the tallest bar each pointer has passed including its own, and always move the pointer on the lower bar. Then every bar already passed is no taller than the taller of the two current bars, because a pointer only steps past a bar no taller than the one under the other pointer.
Say height[left] < height[right]. By the invariant, leftMax is at most height[right], a bar to the right of left. So the right wall of left is at least leftMax, and its level is exactly leftMax, whatever stands between the pointers. When the right bar is lower or equal, the mirror argument settles right.
Algorithm
- Set
left = 0,right = n-1, andleftMax,rightMaxandwaterto 0. - While
left < right: ifheight[left] < height[right], raiseleftMaxtoheight[left]if needed, addleftMax - height[left]and moveleftright. - Otherwise do the same on the right side and move
rightleft. - Return
water. The bar where the pointers meet is the tallest and holds nothing.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
Pitfalls and edge cases
- Adding the water before raising the running maximum. When
height[left]is aboveleftMax, the amount is negative and the total shrinks. - Moving the pointer on the taller bar, whose level is not proved. On
[4, 1, 3, 0, 5]that version returns 4 instead of 8. - Looking only at the nearest neighbours. In
[3, 0, 2, 0, 1, 0, 4]the bar of 1 fills to level 3, set by bars four and two steps away; the answer is 12. - Treating the ends of the array as walls. Water runs off there, so one bar, two bars, or a row that only rises or only falls holds 0.
Frequently asked questions3
What is the time complexity of Trapping Rain Water?
The two pointer solution runs in O(n) time and O(1) extra space, since each step moves one pointer inward. The leftMax and rightMax arrays version is also O(n) time but uses O(n) space. Scanning both sides from every bar is O(n²).
Can Trapping Rain Water be solved with a stack?
Yes. Keep a stack of indices with falling heights. When a taller bar arrives, pop the top: it is the floor of a pool walled by the new top and the current bar. Add (min(two walls) - floor) × (distance between the walls - 1) and keep popping. That fills the water in horizontal layers, in O(n) time and space.
How is Trapping Rain Water different from Container With Most Water?
In Container With Most Water the lines take up no space and the answer is the single largest rectangle between two lines. Here every bar is solid, and the answer sums the water over all bars. Both move the lower side for the same reason: its result is already decided.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def trap(height):
# Write code hereTest #1
Test #2
Test #3
Argument
height = [0, 3, 1, 0, 2, 5, 1, 2]
Expected Output
7