42. Trapping Rain Water
## description
## 42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
1Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
2Output: 6
3Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Example 2:
1Input: height = [4,2,0,3,2,5]
2Output: 9- –n == height.length
- –1 <= n <= 2 * 104
- –0 <= height[i] <= 105
Constraints:
## notes
### Intuition
Water at any position is bounded by the minimum of the maximum heights on its left and right. The two-pointer technique lets us compute this without precomputing all prefix/suffix maximums.
### Implementation
Use left and right pointers at opposite ends, tracking maxL (max height seen from left) and maxR (max height seen from right). Update these maxes on each iteration. If maxL ≤ maxR, we know the left side is the bottleneck—add maxL - height[l] to the answer and move left. Otherwise, the right side is the bottleneck—add maxR - height[r] and move right.
### Edge-cases
The algorithm handles flat terrain (no trapping) naturally since max - height will be zero. Empty arrays or single-element arrays trap no water.
- –Time: O(n) — each element visited once
- –Space: O(1) — only tracking pointers and two max values
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def trap(self, height: List[int]) -> int:
5 maxL, maxR = 0, 0
6 l, r = 0, len(height) - 1
7 trapped = 0
8
9 while l < r:
10 maxL, maxR = max(maxL, height[l]), max(maxR, height[r])
11
12 if maxL <= maxR:
13 trapped += maxL - height[l]
14 l += 1
15 else:
16 trapped += maxR - height[r]
17 r -= 1
18
19 return trapped
20
21
22
23
24
25if __name__ == "__main__":
26 # Include one-off tests here or debugging logic that can be run by running this file
27 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
28 solution = Solution()
29