[LeetCode] Trapping Rain Water

Link : Trapping Rain Water

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!

Analysis :
Each area containing water has a high bar on each side.

First try, go from one side, record highest bar. When seeing lower bar, get height difference and add to water sum. When seeing higher bar, add current area to sum, and set new highest bar and clear current area of water. Problem, cannot solve 423, if only go from left to right.

Second try, because each area of water has two high bar on sides, find highest two bar, and calculate the water sum in between. Get next two high bars(excluding the area traversed). But this needs sorting, compare if bars traversed, and extra space.

Third try, go from both sides. Record not only left highest bar, but also right highest bar. Traverse again and if find any bar higher than current, start accumulating. if no, this bar only serves as a boundary of some possible area of water.

 class Solution {  
 public:  
   int trap(int A[], int n) {  
     if(n<=2)  
       return 0;  
     int sum = 0;  
     int * l = new int[n];  
     int * r = new int[n];  
     l[0] = 0;  
     for(int i=1; i<n; i++)  
       l[i] = A[i-1]>l[i-1] ? A[i-1]:l[i-1];  
     r[n-1] = 0;  
     for(int i=n-2; i>=0; i--)  
       r[i] = A[i+1]>r[i+1] ? A[i+1]:r[i+1];  
     for(int i=1; i<n-1; i++)  
     {  
       int min = l[i] < r[i] ? l[i] : r[i];  
       if(min>A[i])  
         sum += min-A[i];  
     }  
     delete l;  
     delete r;  
     return sum;  
   }  
 };