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: 9
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Intuition
Approach 1:
BruteForce
We at each index, Find Left_max, Right_max
Take min(Left_max, Right_max) - arr[i]
This gives tapped water for a particular index
This is N^2
Approach 2:
Better
Rather than Going and finding the Left_max and Right_max again and again
We, Maintain a Prefix_max and Suffix_max array and Do it in 1 time
This has a
Time = N, Space = N for Matintaing array
Approach 3:
Optimal
Maintain Two pointers,
Here, We maintain Left max and Right max
Now we do
L_max - arr[low]
only when we ensure that there is at least that much on right side
eg-> l =3(2), r=10(2)
Now it enters if condition and Ensures that low<=high
Meaning atleast 2 is present on right side
then when
l=4(1), r10(2)
We know for sure that right has 2 or greater than 2
Hence we directly take l_max = 2 - arr[low]
rather than min(l_max, r_max) - arr[i]
where r_max >= l_max we know
Hence no need of it,
similarly for right side