Trapping Rain Water - LeetCode 42

 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

 

Solution 1(Optimal approach):

Space complexity: O(1), Time complexity: O(n)

class Solution {

    public int trap(int[] height) {

        

        if(height.length==1 || height.length==2)

            return 0;

        

        int n=height.length;

        int maxLeft=height[0],maxRight=height[n-1];

        int trappedWater=0;

        

        int leftptr=1,rightptr=n-2;                       

            

        while(leftptr<=rightptr){

          

          int min=0,diff=0;

            

          if(height[leftptr]>maxLeft)

              maxLeft=height[leftptr];

          if(height[rightptr]>maxRight)

              maxRight=height[rightptr];

            

          if(maxLeft<=maxRight)

          {

            min=Math.min(maxLeft,maxRight);  

            diff=min-height[leftptr];

              leftptr++;

          }else

            {

                min=Math.min(maxLeft,maxRight);

                diff=min-height[rightptr];

                rightptr--;

          }     

            

          trappedWater=trappedWater+diff;  

        }

        return trappedWater;

    }

}

Solution 2: (Space complexity: O(n), Time complexity: O(n))

class Solution {

    public int trap(int[] height) {

        

        if(height.length==1 || height.length==2)

            return 0;

        

        int n=height.length;

        int maxLeft[]=new int[n],maxRight[]=new int[n];

        int trappedWater=0;

        

        int leftMax=0,rightMax=0;                       

        for(int i=0;i<n;i++){

            

            if(height[i]>leftMax)

                leftMax=height[i];

            

            maxLeft[i]=leftMax;

            

        }

        for(int i=n-1;i>=0;i--){

            

            if(height[i]>rightMax)

                rightMax=height[i];

            

            maxRight[i]=rightMax;

            

        }

                               

        for(int i=1;i<n-1;i++){

            

            int min=Math.min(maxRight[i],maxLeft[i]);

            int diff=min-height[i];

            

            trappedWater=trappedWater+diff;

            

        }                       

                               

        return trappedWater;

    }

}