42. Trapping Rain Water

Problem Statement

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

https://leetcode.com/problems/trapping-rain-water/description/

Video Links

https://www.youtube.com/watch?v=m18Hntz4go8&ab_channel=takeUforward

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;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems