Concise (24 lines) C++ Greedy/DP solution with detailed explanation


  • 0
    M

    DP:

    Let f(i) be the number of consecutive integers at index i,

    Transition equation and example:

    f(i) = min {f(j)} + 1,   if j<i && nums[i]==nums[j]+1
            1                 ,   o.w.
    

    This means that for nums[i], we look at all nums[j] with j<i and nums[i] == nums[j] + 1, and we select the nums[j] whose f(j) is the smallest to concatenate with nums[i] (this is why f(i) = min {f(j)} + 1)

    Note that since each number in the array can only be concatenated once, we have to mark a nums[j] as 'used' once it has been selected to concatenate with a nums[i]. This solution is Greedy since for each nums[i], we select the minimum value of f(j)'s from all j's with nums[i] == nums[j]+1, and once we select one nums[j] we mark it as used and never consider it again (so it is some knid of local optima).

    The intuition behind the Greedy solution is that we try to complete a subsequence with shorter length first, for example,

    nums  1 2 3 3 4 4 5 5
    f     1 2 3 1 2 4 3 5
    

    For the first nums[i]==4, we select the one with f[j]==1 instead of the one with f[j]==3 to concatenate since the one with f[j]==1 is the shortest among the two.

    Note that to see if the array can be split into subsequences, we keep a global integer 'count'. Whenever you get an f(i)==3, it means we have got a subsequence of length 3, so you can add 3 to count. And whenever you get an f(i)>3, it means you get an additional element concatenated to a subsequence with length >=3, so you only add 1 to count (since all previous has been added to count).

    In the end, if count == nums.size(), return true since all elements in the array are in some subsequence with length >= 3. Otherwise, return false.

    class Solution {
    public:
        bool isPossible(vector<int>& nums) {
            vector<int> f(nums.size(),1);
            vector<bool> used(nums.size(),false);
            int count = 0;
            for(int i=0; i<nums.size(); i++) {
                int j = i-1, index = -1, fvalue = INT_MAX;
                while(j>=0 && (nums[i]==nums[j] || nums[i]==nums[j]+1)) {
                    if(nums[i]==nums[j]+1 && !used[j]) {
                        if(f[j]<fvalue) {
                            index=j;
                            fvalue=f[j];
                        }
                    }
                    j--;
                }
                if(index!=-1) {
                    used[index]=true;
                    f[i] = f[index]+1;
                    if(f[i]==3) count+=3;
                    else if(f[i]>3) count++;
                }
            }
            return count==(int)nums.size();
        }
    };
    

Log in to reply
 

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