You are given n non-negative integers that describe an elevation map, where each bar has width 1 and height[i] is the height of bar i. After it rains, water collects in the dips between taller bars. Return the total units of water that stay trapped.
- 1 <= height.length <= 2 * 10^4
- 0 <= height[i] <= 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
For each bar, the brute force scans left and right to find the tallest bars, which is O(n^2). Prefix and suffix maximum arrays bring that to O(n) time and O(n) space. With two pointers we can drop the arrays: if leftMax < rightMax, the water at the left pointer is decided by leftMax alone, because some bar on the right is at least as tall as rightMax. So we settle the side with the smaller max and move that pointer.
Algorithm
- Set
l = 0,r = n - 1,leftMax = rightMax = 0,water = 0. - While
l < r, updateleftMaxwithheight[l]andrightMaxwithheight[r]. - If
leftMax < rightMax, addleftMax - height[l]and movelright. - Otherwise add
rightMax - height[r]and moverleft. - Return
water.
O(n)Space: O(1)class Solution: def trap(self, height: List[int]) -> int: l, r = 0, len(height) - 1 left_max = right_max = water = 0 while l < r: left_max = max(left_max, height[l]) right_max = max(right_max, height[r]) if left_max < right_max: water += left_max - height[l] # left side is limited by left_max l += 1 else: water += right_max - height[r] # right side is limited by right_max r -= 1 return water