My solution----inspired by 2 sum


  • 16
    P

    This code looks like O(n) algorithm of the question 2 sum:

    int trap(int A[], int n) {
        if (n == 0) return 0;
        int l = 0, r = n - 1;
        int lv = A[l], rv = A[r];
        int total = A[l] + A[r], rainTotal = total;
        while (l != r)
        {
            if (A[l] < A[r])
            {
                l++;
                total += A[l];
                lv = max(lv, A[l]);
                rainTotal += lv;
            }
            else
            {
                r--;
                total += A[r];
                rv = max(rv, A[r]);
                rainTotal += rv;
            }
        }
        return rainTotal - total;
    }
    

    lv is A[0...l]'s max value, rv is A[r...n-1]'s max value.
    rainTotal is the total volume after raining, total is Sigma(A[0...n-1])


  • 0
    X

    Hi! Would you please explain more specifically how did you relate this problem to the 2-sum problem? Thank you!


  • 0
    A

    Nice solution :),loved it,fullarea-the total sum of the discrete values


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.