Trapping Rain Water
- 4 min read
- LC-Hard
- Two Pointers
3 years ago
Solution - O(n) memory
- At each point in the array, the height is determined by the lower of the two max heights to the left and right.
- For any point in the array, we need to consider the max height to the right, and the max height to the left.
- Take the minimum of these values, and multiply it by the height to get the water that can be trapped.
Solution - O(1) memory
- The bounding conditions (i.e. how much water can be stored at a particular point) is determined very similarly to the problem Container with Most Water
- The amount of water that can be trapped is determined by the lower height. The lower height is the bottleneck- it doesn't matter how high the other height is. This is why below, we change whichever height is greater. (between left_max and right_max)
- Maintain two pointers,
landr, initialized to first and last of the array. - Also maintain two variables,
max_landmax_r, initially the height of the map at the pointers above. - At each iteration, whichever of the pointer (
max_landmax_r) is shorter, the increment the respectiverorlpointer - Why? Because out of two heights, the shorter one is going to be the limiting factor. No matter how long the other higher height is, we can only trap more water if the lower height (our bottleneck) becomes higher.
- If
max_lis less thanmax_r, it means that the current pointerlis at a lower elevation, so we move it forward. And vice versa forr(if that is the case) - The amount of water that can be trapped is the difference between
max_landheight[l] - At any height, the amount of water you can trap is determined by the height of the left and right indices. It doesn't matter how far away they are, and thus, for our purposes, we can assume that they're close by (the index right after). However far they are, the max height on either side is what is most important. Among both these heights, the smaller height is obviously going to be the bottleneck.
- We increment the pointer first because the index it was previously at, we've already accounted for.
- We cannot store water in the extremities of the array, so this edge case is automatically taken care of.
- Only after checking which of the max_l and max_r is smallest, we begin to move the l or r pointer
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def trap(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
left_max, right_max = height[l], height[r]
ans = 0
while l < r:
if left_max < right_max:
l += 1
ans += max(0, left_max - height[l])
left_max = max(left_max, height[l])
else:
r -= 1
ans += max(0, right_max - height[r])
right_max = max(right_max, height[r])
return ans
Another Solution that's the same but code intuitively makes more sense because I did it on the first try while being 1 month off LeetCode, 5 hours of sleep, and no coffee
def trap(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
max_l, max_r = height[l], height[r]
amount_trapped = 0
while l <= r:
if max_l < max_r:
amount_trapped += max(0, max_l - height[l])
max_l = max(max_l, height[l])
l += 1
else:
amount_trapped += max(0, max_r - height[r])
max_r = max(max_r, height[r])
r -= 1
return amount_trapped
The above solution also works when you're l and r pointers start out and 1 and len(height) - 2 because you can't store water at the extremities