Novel and easy to understand O(n) solution with full explanation in C++


  • 2
    X

    For more info, please refer to my blog post.

    class Solution {
    public:
        int trap(int A[], int n) {
            int i, j, volume;
            int sum = 0;
    
            if (n <= 0) return 0;
            // visited[i]: is equal sided container counted
            bool visited[n] = {false};
            
            // containers w/ left side strictly lower or equal to right side
            i = 0;
            while (i < n) {
                // find right side, i.e., first higher point
                for (j = i + 1, volume = 0; j < n && A[j] < A[i]; j++) {
                    volume += A[i] - A[j];
                }
                // found one container; this also holds when j = i + 1 since volume is 0
                if (j < n) {
                    visited[i] = A[j] == A[i];
                    sum += volume;
                }
    
                i = j;
            }
    
            // containers w/ right side strictly lower
            i = n - 1;
            while (i >= 0) {
                // find left side
                for (j = i - 1, volume = 0; j >= 0 && A[j] < A[i]; j--) {
                    volume += A[i] - A[j];
                }
                // do not double count equal sided containers
                if (j >= 0 && !visited[j])
                    sum += volume;
                
                i = j;
            }
        
                return sum;
            }
        };
    

  • 0
    P

    you can avoid using an extra bool vector by checking the if (a[j] >= a[i]) for left side and checking if (a[j] > a[i]) for right side. Otherwise, excellent solution!


Log in to reply
 

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