Coding Series : #Problem1 - Trap Rain water

Problem Statement : You have been given a non - negative integer arrays which represent an elevation map where width of each bar is 1 , find out how much water can be trapped after rain.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] , Output : 6

First Thought ???? ?? ?? ?? ?? I should find out how much water can get stuck between two bars and add them . NO????????

Well, you can solve that way but try that your variable should be one which means focus on one bar at a time. Think how much water can be accumulated on top of every bar after rain. So, water can accumulate on top of a bar only when there is elevation on both the sides and there will be a pit formation on top of the bar. So, we need to find the depth of possible pit over every bar.

Find the depth of possible pit on top of every bar. Assume , Height of i'th bar is H(i) - First we will find the height of tallest bar (maximum elevation) on left of the i'th bar , say it is called maxLeftElevation(i), and then find the height of tallest bar (maximum elevation) on right side of the i'th bar and call it maxRightElevation(i). Pit formed on top of i'th bar will start from H(i) and end at smaller bars represented by either maxLeftElevation or maxRightElevation.

Water stored on top ith bar = min(maxLeftElevation,maxRightElevation) - H(i)

Brute Force Approach : Iterate over the array and for each height, h(i) - > iterate to the left side of the array and right side of the array to find the maxLeftElevation and maxRightElevation and then find pitDepth = min(maxLeftElevation, maxRightElevation) - h(i) . if this value is greater than 0 then add it to the result. Time complexity : O(n2) , Space Complexity :O(1). Find the code below : -

public int trap(int[] height) 
    int result = 0, leftMaxElevation = 0 , rightMaxElevation = 0;
    //for each bar, find out the maximum elevation on left and right.
    for(int i = 0 ; i < height.length; i++){
        leftMaxElevation = 0;
        rightMaxElevation = 0;
        //find maximum left elevation 
        for(int left = 0; left < i ; left++){
         leftMaxElevation = Math.max(leftMaxElevation,height[left]);
        }
        //find maximum right elevation 
        for(int right = i+1; right < height.length ; right++){
          rightMaxElevation=Math.max(rightMaxElevation,height[right]);
        }
        //calculate shorter elevation between right and left elevation
        int minElevation=Math.min(leftMaxElevation,rightMaxElevation);
        //Find the pit depth.
        int currentWaterTrapped = minElevation > height[i] ? 
                                  minElevation - height[i] : 0;
        //Add all the put depths.
        result+=currentWaterTrapped;
    }
{        

Two Pointer Approach : In this approach , we start 2 pointers one from left and one from right. We compare between these two bars represented by the two pointers. Suppose left side bar is smaller than right side bar, this means that this left bar has guaranteed elevation on the right hand side. Now , it just needs on find out whether it has left elevation or not. if this left bar is taller than leftMaxElevation then just update the leftMaxElevation and move ahead otherwise, find out the difference in height of this bar and leftMaxElevation and update the result. Same logic goes in case right bar is smaller than left bar. Time complexity : O(n) , Space Complexity :O(1). Find the code below -

public int findTrappedWaterTwoPointer(int[] height) 
            int left = 0 , right = height.length - 1;
            int result = 0, leftMaxElevation = 0, rightMaxElevation = 0;
            while(left < right){
           //Find the smaller bar between left bar and right bar.
           //If one side bar is taller,process the opposite side elevation
           //if bar pointed by left pointer is smaller
           //process leftMaxElevation because
           //we have already found that there is a taller bar on right
            if(height[left] < height[right]){
                    //if there is no elevation on the left side.
                    if(height[left] >= leftMaxElevation){
                        leftMaxElevation = height[left];
                    }else{
                   //We have found a pit and its depth will be equal
                   //to difference between left elevation and height of bar
                        result += leftMaxElevation - height[left];
                    }
                    left++;
                }else{
              //Here, right side bar is smaller.
              //Find if there is elevation on right side of the bar or not.
                    if(height[right] >= rightMaxElevation){
              //No elevation found on right side, just update the elevation
                        rightMaxElevation = height[right];
                    }else{
                        //we have found elevation on the right side as well
                        //find the depth of the pit.
                        result += rightMaxElevation - height[right];
                    }
                    right--;
                }
            }
            return result;


}
{