Trapping Rain Water

Trapping Rain Water

AC Rate: 165/540

My Submissions

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.

Algorithm:

scan from left to right get the leftMostHeight

scan from right to left get the rightMost Height

at the pos i, if(A[i] < min(left, right)) trap[i] = min(left, right) – A[i];

class Solution {

public:

       int trap(int A[], int n) {

              // Start typing your C/C++ solution below

              // DO NOT write int main() function

              if(n < 3) return 0;

              int *leftmost = new int[n];

              int max = A[0];

              leftmost[0] = A[0];

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

                     if(A[i] > max) max = A[i];

                     leftmost[i] = max;

              }

              int sum = 0;

              max = A[n-1];

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

                     if(min(leftmost[i], max) > A[i])

                           sum += min(leftmost[i], max) - A[i];

                     if(A[i] > max) max = A[i];

              }

              delete [] leftmost;

              return sum;

       }

};