9-liner beat 98.8%, no set, vector hasher or helper function (detailed explanation)


  • 1

    This is a rewritten version from @Mxxx's great solution which does not use set, DFS or vector hasher. (I give my applause to the latter especially)

    In my opinion, the challenge of this problem is actually how to detect and avoid duplicated subsequences in the result. Many fellow coders used set of arrays to automatically avoid duplicates. However, I do not quite prefer this strategy because

    • not every programming language provides default hasher for vectors and
    • hash to compare vectors might not be cheap.

    In other words, because vector is not a sigular data structure which contains O(N) amount of data, any sort of hash/comparison of vector's to check duplicates will not be cheap, and we should avoid to do so.

    Simple Case: If given array a[] has distinct numbers, the algorithm will be trivial to employ DP directly without worry for duplicates. Consider how many new increasing subsequences from a[0:i] compared with a[0:i-1]:

    1. for any a[j] < a[i], construct size 2 array {a[j], a[i]};
    2. for any increasing subsequence seq in a[0:i-1], if seq.back() < a[i], construct a new sequence by appending a[i] to seq.

    General Case: When a[] has duplicates, simply appending last entry to the results of previous arrays will certainly cause duplicates. Well, the duplicates are caused by the identical values which already appear in previous increasing subsequences. So we can decompose previous result into segments with each segments containing the new subsequences.

    Use d[i] = 0 or 1 to denote if value a[i] already appeared in the array previously. Use index interval [s[i], s[i+1]) to denote the index range of new sebsequences contributed by a[i].

    Consider array a[] = {1, 2, 1, 2} with initial result res = {}, scan from left and we have,

    • {[1], 2, 1, 2}: s[0] = 0, d[0] = 0, res = {};
    • {1, [2], 1, 2}: s[1] = 0, d[1] = 0, res = {[1,2]};
    • {1, 2, [1], 2}: s[2] = 1, d[2] = 1, res = {[1,2], [1,1]};
    • {1, 2, 1, [2]}: s[3] = 2, d[3] = 1, res = {[1,2], [1,1], [1,1,2], [2,2], [1,2,2]}.

    Note that when last 2 is scanned, we go backward to check each previous entry:

    • a[2] = 1 is a duplicate, so do not construct [1,2]. Only append 2 to the result contributed by a[2], i.e., [1,1]+2;
    • a[1] = 2 is not a duplicate, so construct [2,2]. append 2 to the result contributed by a[1], i.e., [1,2]+2. Then we found that a[1] is duplicated with the currently scanned a[3] and there will be no more new sequences because any sequences constructed before a[1] are already appended bya[1] which is same as a[3].

    Therefore, [1,1,2], [2,2], [1,2,2] are the new additions when last 2 is scanned.

        vector<vector<int>> findSubsequences(vector<int>& a) {
            if(a.size() < 2) return {};
            vector<vector<int>> res; int s[a.size()], d[a.size()], j;
            for(int i=0; i<a.size(); ++i)
                for(j=i-1, s[i]=res.size(), d[i]=0; j>=0; --j)
                    if(a[j] <= a[i]) {
                        if(!d[j]) res.push_back({a[j], a[i]});
                        for(int k=s[j];k<s[j+1];++k) res.push_back(res[k]), res.back().push_back(a[i]);
                        if(d[i] = a[j]==a[i]) break;
                    }
            return res;
        }
    

Log in to reply
 

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