Leetcode:Trapping Rain Water (8ms) Analysis & solution

PROBLEM:

Given n non-negative integers representing an elevation map where the width of each bar is 1, 

compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map 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. Thanks Marcos for contributing this image!

Hide Tags

 Array Stack Two Pointers

Show Similar Problems

Analysis:

Method 1:

The index of  i is sweeping from left to right. Two pointers: start and end, are used to temporally store the index of a convex. Then we  do summation when the two are found. And continue until the end.....

The keys are that we need to consider all possible conditions. Three conditions should be considered in the following figure, labeled as 1~3:

If you can cover all above cases, it's not difficult to coding. Usually, it's really difficult to identify all possible cases when start to coding. Problem arises when new case appear. So lots of time were wasted on finding the cases. I don't think it's a good problem to enhance the coding ability! 
Therefore, don't waste your time on this method!!

Method 2:
Another smarter method is:
1. find out the index of largest item
2. for left part of the index, the trapped water for each unit depends on the left highest item.
3. for right part of the index, the trapped water for each unit depends on the right highest item.
see figure below:

The logic is simple and don't need to consider so many cases in method 1. So, strategy is much more important than coding itself!!

method 1:

///////////////////////////////////////////////////////////////////////////////

//codes 8ms

class Solution {

public:

       int trap(vector<int>& height) {

              int start = 0, end = -1;

              int sFlag = 0, sum = 0;

              //check input

              if (height.size()<3)return 0;

              //sweep i from left to right

              for (int i = 1; i<height.size(); i++){

                     //identify start and end

                     if (sFlag == 0 && height[i]<height[i - 1]){

                           start = i - 1;

                           sFlag = 1;

                     }

                     else if (sFlag == 1 && end == -1)end = height[i] > height[i - 1] ? i : -1;

                     //case 1

                     else if (sFlag == 1 && end !=-1)end = height[i] > height[end] ? i : end;

                     //identify when to do summation

                     if (sFlag==1 && end!=-1){

                           if (height[end] >= height[start] || (i == height.size() - 1 ))

                           {

                                  int tmp = height[start] > height[end] ? height[end] : height[start];//choose the lower lever

                                   for (int j = start+1; j<end; j++){

                                         int sTmp = (tmp - height[j]) > 0 ? (tmp - height[j]) : 0;//case 2: prevent negtive value

                                         sum += sTmp;

                                  }

                                  //case 3

                                  if (i == height.size() - 1 && end != height.size() - 1){

                                         i = end - 1;

                                  }

                                  sFlag = 0;

                                  end = -1;

                           }

                     }

              }

              return sum;

       }

};

//////////////////////////////////////

method 2

////////////////////////////////////////

class Solution {
public:
       /*
        //function of finding the highest value in ...
        int findHighest(int left, int right, vector<int>& height){
            int maxH=0;
            for (int i=left;i<=right;i++){
                if(height[i]>maxH)maxH=height[i];
            }
            return maxH;
        }
        */

    int trap(vector<int>& height) {
        //corner case
        if (height.size()<3)return 0;

        //find the highest point
        int hMax=height[0], idx=0;
        for (int i=0;i<height.size();i++){
            if (height[i]>hMax) {hMax=height[i]; idx=i;}
        }
        
        int sum=0, maxTmp=height[0];
        //for left part
        for (int i=1;i<idx;i++){
            if (height[i]>maxTmp){
                maxTmp=height[i];
            }
            sum=maxTmp-height[i] >0 ?sum+maxTmp-height[i]:sum;
        }
        
        
        //for right part
        maxTmp=height[height.size()-1];
        for (int i=height.size()-1;i>idx;i--){
            
            
            if (height[i]>maxTmp){
                maxTmp=height[i];
            }
            sum=maxTmp-height[i] >0 ?sum+maxTmp-height[i]:sum;
        }        
        
        
        /*
        //for left part
        int sum=0;
        for (int l=idx-1;l>0;l--){
            int tmpMax=findHighest(0,l,height);
            sum=tmpMax-height[l] >0 ?sum+tmpMax-height[l]:sum;
            
        }
        //for right part
        for (int r=idx+1;r<height.size();r++){
            int tmpMax=findHighest(r,height.size()-1,height);
            sum=tmpMax-height[r] >0 ?sum+tmpMax-height[r]:sum;
            
        }        
        */
        return sum;
  
        
    }

};