O(n) solution c++


  • 0
    P
    class Solution {
    public:
        int trap(int a[], int n) {
            int tot = 0;
            if (n < 3) return 0;
            int v = 0;
            int h = a[0];
            int i = 1;
            vector<bool> included(n,false);
            // case 1 : enclosed by left side
            while (i < n) {
                h = a[i-1];
                while(i < n && a[i] < h) {
                    v += h-a[i];
                    i++;
                }
                
                if (i < n && a[i] >= h && v > 0) {
                    tot += v;
                    v = 0;
                }
                i++;
            }
            i = n-2;
            h = a[n-1];
            v = 0;
            // case 2 enclosed by right side
            while(i >= 0) {
                h = a[i+1];
                while(i >= 0 && a[i] < h) {
                    v += h-a[i];
                    i--;
                }
                
                if (i >= 0 && a[i] > h && v > 0) {
                    tot += v;
                    v = 0;
                }
                i--;
            }
            return tot;
        }
    };

Log in to reply
 

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