[LeetCode] 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.

11

 

SOLUTION 1:

For each bar, check if the current bar can be a left-wall of a container, for those can not be a left-wall, we assume it is inside the container. By walking through the array, we always renew the height of current container.

Code:

class Solution {
public:
    bool searchHeight(int height, int p, int n, int A[]){
        for(int i = p+1; i<n; i++){
            if(A[i] >= height) return true;
        }
        return false;
    }

    int trap(int A[], int n) {
        if(n <= 2) return 0;
        int p1 = 0;
        int p2 = 0;
        int count = 0;
        int top = 0;
        while(p2 < n-1){
            if(p1 == p2){
                if(A[p1] <= A[p1+1]){
                    ++p1;
                    ++p2;
                }else{
                    for(int i=A[p1]; i>A[p1+1]; i--){
                        if(searchHeight(i, p1, n, A)){
                            top = i;
                            --p1;
                            break;
                        }
                    }
                    ++p1; 
                    ++p2;
                }
            }else{
                if(A[p2] < top){
                    count += top - A[p2];
                    ++ p2;
                }else{
                    p1 = p2;
                }                
            }
        }
        return count;
    }
};

SOLUTION 2:

Using Dynamic Programming method, first search forward, record the highest bar before current one, and then search backward, record the highest bar that behind the current one. Then for each bar, it can contain min(maxLeft[i], maxRight[i]) – A[i] size of water.

Code:

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

🙂

This entry was posted in Algorithm, Dynamic Programming, LeetCode and tagged , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*