Trapping Rainwater Problem | Leetcode #42

This video explains a very important programming interview problem which is the trapping rainwater problem.In this problem, given an array representing elevation map, we are required to find the amount of water the elevation map can trap.I have explained all the approaches for solving this problem starting from the bruteforce approach to the most optimal approach.I have shown how we can process and highly optimize the time complexity.

CODE

CODE

//1st Optimal Approach O(N) SPACE
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n<=2)    //We need atleast 3 bars to be able to trap water
            return 0;
        
        vector<int> left(n),right(n);
        left[0] = 0;
        int leftMax = height[0];
        for(int i=1;i<n;++i) {  //Store the leftMax for each bar
            left[i] = leftMax;
            leftMax = max(leftMax,height[i]);
        }
        
        right[n-1] = 0;
        int rightMax = height[n-1];
        for(int i=n-2;i>=0;--i) {   //Store rightMax at each bar
            right[i] = rightMax;
            rightMax = max(rightMax,height[i]);
        }
        
        //Now parse the array to find the water
        int trappedWater = 0;
        for(int i=1;i<n-1;++i) {    //Find trappedWater
            if(height[i]<left[i] and height[i]<right[i])
                trappedWater += min(left[i],right[i]) - height[i];
        }
        return trappedWater;
    }
};

//Optimal O(1) SPACE
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n<=2)
            return 0;
        
        int maxLeft = height[0];
        int maxRight = height[n-1];
        int trappedWater = 0;
        int left = 1;   //Left pointer
        int right = n-2;    //Right pointer
        while(left<=right) {
            if(maxLeft<maxRight) {
                if(height[left]>=maxLeft)
                    maxLeft = height[left];
                else
                    trappedWater += maxLeft-height[left];
                left+=1;
            } else {
                if(height[right]>maxRight)
                    maxRight = height[right];
                else
                    trappedWater += maxRight-height[right];
                right-=1;
            }
        }
        return trappedWater;
    }
};

Leave a Reply