Published: Sep 18, 2022
This problem might look like monotonic stack or dynamic programming. Both work, however, two pointers approach also works well. The trapped water is bounded by a lower height of left and right. Keep tracking the lower height is a key to solve this problem
nnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
n == height.length
1 <= n <= 2 * 10**4
0 <= height[i] <= 10**5
Example 1 Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: 6 units of rain water (blue section) are being trapped.
Example 2 Input: height = [4,2,0,3,2,5] Output: 9
Here, two pointers approach is taken. The pointers start from leftmost and rightmost indicies. Set initial max heights for both left and right with the value of leftmost and rightmost indices. The total trapped water is bounded by the lower height, so take (the lower side max height - bar height at lower side height) and add it up to the total. Then increment the pointer and maintain the max heights.
class TrappingRainWater: def trap(self, height: List[int]) -> int: n = len(height) if n < 3: return 0 left, right, total = 0, n - 1, 0 left_max, right_max = height[left], height[right] while left < right: if left_max <= right_max: total += left_max - height[left] left += 1 left_max = max(left_max, height[left]) else: total += right_max - height[right] right -= 1 right_max = max(right_max, height[right]) return total