42. Trapping Rain Water — LeetCode(Python)
I got you!
Problem:
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:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 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:
Input: height = [4,2,0,3,2,5]
Output: 9Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
Solution:
l, r = 0, len(height) - 1
maxL, maxR = height[l], height[r]
water = 0
while l < r:
if maxL < maxR:
l += 1
maxL = max(maxL, height[l])
water += maxL - height[l]
else:
r -= 1
maxR = max(maxR, height[r])
water += maxR - height[r]
return waterExplanation —
We use a two-pointer approach here.
We initialize two pointers at two ends of the array.
We store the maximum left height and maximum right height of our given container.
Then, we shrink the size of our window by incrementing the left pointer or decrementing the right one.
If the maximum left height is less than the maximum right height, we increment our left pointer, update our maximum left height if the new index has a height greater than maxL, and append the water contained.
Similarly, otherwise, we increment our right pointer, update our maximum right height if the new index has a height greater than maxR, and append the water contained.
The water contained is the difference between the min(maxL, maxR) and height[i] of that index.
The water variable is then finally returned.
Time and Space Complexity —
Since we are iterating through the array only once, our code requires linear runtime. Also, we require a constant amount of extra space.
Thus, if n is the length of the array nums,
Time Complexity: O(n)
Space Complexity: O(1)
