Water Held Between Bars
Problem
A row of bars of width 1 stands on flat ground, with heights given as non-negative whole numbers. After heavy rain, water settles in the dips between bars and anything above the lower of the surrounding walls runs off. Return the total units of water the row holds. Answer with one pass and constant extra memory.
Examples
Input: heights = [3, 0, 2, 0, 4, 1, 2]
Output: 8
Why: 3 + 1 + 3 units between the 3 and the 4, and 1 unit over the 1Input: heights = [1, 2, 3, 4]
Output: 0
Why: a staircase has no dip for water to sit inInput: heights = []
Output: 0
Why: edge case, no bars hold no waterHints
0 / 3
Look at one bar at a time. The water above it is set by the tallest bar to its left and the tallest bar to its right, whichever of those two is lower, minus its own height.
Storing the tallest bar on each side for every position takes two extra lists. As in the container lesson, two pointers moving inward from the ends can do without them, as long as you always move the side with the shorter wall.
Keep a pointer at each end and the tallest height seen so far from each side. If the left bar is lower than the right bar, the left side's tallest height is the limiting wall for the left bar, so add that height minus the bar and step right. Otherwise do the mirror image on the right side.
Solution
The water above a bar is the lower of the tallest bar on its left and the tallest bar on its right, minus the bar's height. When the left bar is lower than the right bar, some bar at least that tall exists on the right, so the left side's running maximum is the true limit for the left bar even though the right side is not fully known. The mirror argument covers the right bar, so each step settles one bar exactly, just as the container problem always moves the shorter wall. Time is O(n) and space is O(1).
def trapped(heights):
i, j = 0, len(heights) - 1
left_max = right_max = water = 0
while i < j:
if heights[i] < heights[j]: # the right side is tall enough: left wall decides
left_max = max(left_max, heights[i])
water += left_max - heights[i]
i += 1
else: # the left side is tall enough: right wall decides
right_max = max(right_max, heights[j])
water += right_max - heights[j]
j -= 1
return water
print(trapped([3, 0, 2, 0, 4, 1, 2])) # -> 8
print(trapped([1, 2, 3, 4])) # -> 0
print(trapped([])) # -> 0Stuck on the idea rather than the code? Container With Most Water covers it.