Trapping Rainwater 🌊

Today's Question:

It's a rainy day, and you are given n bars, each of 1 unit in width. How will you calculate the amount of water trapped between them? 🌧️ 

First try to solve the problem here: https://leetcode.com/problems/trapping-rain-water/

Stuck? 🤔 

No worries, I've got you covered!!

Let's think on it💭 

We need to figure out how many water units will be trapped after it rains...How can we do this?

Total water means we can calculate the individual water stored by each bar and sum it up. Sounds right?

Yes, so to calculate the individual water stored, we must know from which bar to which bar the water is being stored ... Can we find the maximum bar on both sides of the element?

YES! leftMax & rightMax

But water won't be trapped up to the height of the larger one among the leftMax & rightMax.

So, we need to get the minimum (leftMax, rightMax).

And since we are trying to find the amount of water trapped, we need to know the remaining height for each bar for which the water will be trapped.

Therefore, we will subtract the height of the bar from minimum (leftMax, rightMax) for each bar and then sum it up to get the total water.

Algorithm:

• Take maximum of left and side parts of a given bar.
• Get the water for each bar by min(leftMax, rightMax) - bar[i].
• Sum up the water.

int trap(vector<int>& height) {

        int n = height.size(); 
        int waterSum = 0;
        for(int i=0; i<n; i++){

            int leftMax = 0, rightMax = 0;
            for(int j=i; j>=0; j--){
                leftMax = max(leftMax,height[j]);
            }

            for(int j=i; j<n; j++){
                rightMax = max(rightMax,height[j]);
            }

            int h = min(leftMax,rightMax); 
            waterSum+=h-height[i];
        }

        return waterSum;
    }

• Complexity: Time: O(N*N) Space: O(1)

Time complexity is increasing in this solution. To reduce this, we can store the leftMax and rightMax in separate arrays as follows.

int trap(vector<int>& height) {

        int n = height.size();
        vector<int> water;

        vector<int> l(n);
        vector<int> r(n);
        l[0]=height[0];
        r[n-1]=height[n-1];

        for(int i=1; i<n; i++){
            l[i]=max(l[i-1],height[i]);
        }

        for(int i=n-2; i>=0; i--){
            r[i]=max(r[i+1],height[i]);
        }

        for(int i=0; i<n; i++){
            int a = min(l[i],r[i]);
            water.push_back(a-height[i]);
        }

        int x = accumulate(water.begin(),water.end(),0);
        return x;
    }

• Complexity: Time: O(N) Space: O(N)

To further optimize this, we can make the space complexity O(1) from O(N).

How will we do this?

Well, we can use Two-Pointer Approach. In this, left pointer will be at the start of the array and right pointer will be at the end.

Whenever the left element is small or equal to the right one, we have two options:

1. Check if it is the maximum on the left side. If so, update the leftMax. Else,
2. Because there will always be a bar on the right side that is greater than height [left], we can sum it up in ans by subtracting height [left].

And if the right element is smaller than the left one, we can do the same two options but for the right side.

 int trap(vector<int>& height) {

        int n = height.size();
        int leftMax = 0, rightMax = 0, left=0, right=n-1, ans=0;

        while(left<=right){

            if(height[left]<=height[right]){
                if(leftMax<= height[left]){
                    leftMax= height[left];
                } else{
                    ans +=leftMax-height[left];
                }
                left++;
            } 
            else{
                if(height[right]>=rightMax){
                    rightMax = height[right];
                } else{
                    ans +=rightMax-height[right];
                }
                 right--;
            }
        }
        return ans;
    }

• Complexity: Time: O(N) Space: O(1)

That's all for this one! Thankyou for reading till the end. 😃

Synopsis:

For brute force, find the maximum of both sides and sum it for each bar.

A better approach would be to store the left and right maximums in separate arrays.

Two-pointer is the best approach.

✒ New to my blog?

Hey! I am Kanak.

I am a MERN stack developer and an open-source enthusiast. I write on data structures and algorithms and develop cheat-sheets on DSA topics. I have also documented my DSA journey on Twitter for the last 2 months.

Follow me for more such content. 🎉