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
Links
Video Links
Approach 1:
Better
C++
class Solution {
public:
int trap(vector<int>& arr) {
int n = arr.size();
vector<int> pre(n,-1), suf(n,-1);
for(int i=0; i<n; i++){
if(i==0)
pre[i] = arr[i];
else
pre[i] = max(pre[i-1], arr[i]);
}
for(int i=n-1; i>=0; i--){
if(i==n-1)
suf[i] = arr[i];
else
suf[i] = max(suf[i+1], arr[i]);
}
int ans=0;
for(int i=0; i<n; i++){
ans += min(pre[i], suf[i]) - arr[i];
}
return ans;
}
};
Approach 2:
Optimal
C++
class Solution {
public:
int trap(vector<int>& arr) {
int n = arr.size();
int low=0, high=n-1, l_max=0, r_max=0, ans=0;
while(low<=high){
if(arr[low]<=arr[high]){
if(arr[low]>=l_max)
l_max = arr[low];
else
ans += l_max-arr[low];
low++;
}
else{
if(arr[high]>=r_max)
r_max = arr[high];
else
ans += r_max-arr[high];
high--;
}
}
return ans;
}
};
