The problem
An elevation map is given as height: bar i is height[i] tall and 1 wide. After it rains, how many units of water are trapped between the bars?
Examples
01
- Input
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
- Output
6
02
- Input
height = [4, 2, 0, 3, 2, 5]
- Output
9
Constraints
- 1 ≤ height.length ≤ 2 × 10⁴
- 0 ≤ height[i] ≤ 10⁵
The idea
The water above bar i rises to the lower of two walls: the tallest bar on its left and the tallest bar on its right. It holds min(leftMax, rightMax) − height[i] units.
Two pointers avoid storing those maxima. Keep l and r at the ends with leftMax and rightMax. If height[l] < height[r], there is a wall on the right at least as tall as anything on the left, so the left side’s level is exactly leftMax: add leftMax − height[l] and step l in. Otherwise do the same from the right.
- Time
- O(n) — one pass
- Space
- O(1)
Solution · every language run against every case
class Solution: def trap(self, height: List[int]) -> int: l, r = 0, len(height) - 1 left_max = right_max = 0 water = 0 while l < r: # The lower side decides: its water level is its own tallest wall so far, # because the other side is known to have a taller one. if height[l] < height[r]: left_max = max(left_max, height[l]) water += left_max - height[l] l += 1 else: right_max = max(right_max, height[r]) water += right_max - height[r] r -= 1 return water