Java O(n) time & O(1) space solution


  • 28
    F

    The basic idea is that, for each distinct element ele in the input array, we only need to maintain three pieces of information: the number of consecutive subsequences ending at ele with length of 1, length of 2 and length >= 3.

    The input array will be scanned linearly from left to right. Let cur be the element currently being examined and cnt as its number of appearance. pre is the element processed immediately before cur. The number of consecutive subsequences ending at pre with length of 1, length of 2 and length >= 3 are denoted as p1, p2 and p3, respectively. There are two cases in general:

    1. cur != pre + 1: for this case, cur cannot be added to any consecutive subsequences ending at pre, therefore, we must have p1 == 0 && p2 == 0; otherwise the input array cannot be split into consecutive subsequences of length >= 3. Now let c1, c2, c3 be the number of consecutive subsequences ending at cur with length of 1, length of 2 and length >= 3, respectively, we will have c1 = cnt, c2 = 0, c3 = 0, which means we only have consecutive subsequence ending at cur with length of 1 and its number given by cnt.

    2. cur == pre + 1: for this case, cur can be added to consecutive subsequences ending at pre and thus extend those subsequences. But priorities should be given to those with length of 1 first, then length of 2 and lastly length >= 3. Also we must have cnt >= p1 + p2; otherwise the input array cannot be split into consecutive subsequences of length >= 3. Again let c1, c2, c3 be the number of consecutive subsequences ending at cur with length of 1, length of 2 and length >= 3, respectively, we will have: c2 = p1, c3 = p2 + min(p3, cnt - (p1 + p2)), c1 = max(cnt - (p1 + p2 + p3), 0). The meaning is as follows: first adding cur to the end of subsequences of length 1 will make them subsequences of length 2, and we have p1 such subsequences, therefore c2 = p1. Then adding cur to the end of subsequences of length 2 will make them subsequences of length 3, and we have p2 such subsequences, therefore c3 is at least p2. If cnt > p1 + p2, we can add the remaining cur to the end of subsequences of length >= 3 to make them even longer subsequences. The number of such subsequences is the smaller one of p3 and cnt - (p1 + p2). In total, c3 = p2 + min(p3, cnt - (p1 + p2)). If cnt > p1 + p2 + p3, then we still have remaining cur that cannot be added to any subsequences. These residue cur will form subsequences of length 1, hence c1 = max(cnt - (p1 + p2 + p3), 0).

    For either case, we need to update: pre = cur, p1 = c1, p2 = c2, p3 = c3 after processing the current element. When all the elements are done, we check the values of p1 and p2. The input array can be split into consecutive subsequences of length >= 3 if and only if p1 == 0 && p2 == 0.

    Here is the O(n) time and O(1) space Java solution:

    public boolean isPossible(int[] nums) {
        int pre = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
        int cur = 0, cnt = 0, c1 = 0, c2 = 0, c3 = 0;
            
        for (int i = 0; i < nums.length; pre = cur, p1 = c1, p2 = c2, p3 = c3) {
            for (cur = nums[i], cnt = 0; i < nums.length && cur == nums[i]; cnt++, i++);
                
            if (cur != pre + 1) {
                if (p1 != 0 || p2 != 0) return false;
                c1 = cnt; c2 = 0; c3 = 0;
                    
            } else {
                if (cnt < p1 + p2) return false;
                c1 = Math.max(0, cnt - (p1 + p2 + p3));
                c2 = p1;
                c3 = p2 + Math.min(p3, cnt - (p1 + p2));
            }
        }
        
        return p1 == 0 && p2 == 0;
    }
    

  • 0
    J

    Interesting and smart solution. I have one question, why is it O(n) not O(n^2)? I see two for loops, the outer loop is O(n) and the worst case for the inner loop is O(n) if the number of elements with same values is close to n. Did I miss something? Thanks.

    @fun4LeetCode said in Java O(n) time & O(1) space solution:

    public boolean isPossible(int[] nums) {
    int pre = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
    int cur = 0, cnt = 0, c1 = 0, c2 = 0, c3 = 0;

    for (int i = 0; i < nums.length; pre = cur, p1 = c1, p2 = c2, p3 = c3) {
        for (cur = nums[i], cnt = 0; i < nums.length && cur == nums[i]; cnt++, i++);
            
        if (cur != pre + 1) {
            if (p1 != 0 || p2 != 0) return false;
            c1 = cnt; c2 = 0; c3 = 0;
                
        } else {
            if (cnt < p1 + p2) return false;
            c1 = Math.max(0, cnt - (p1 + p2 + p3));
            c2 = p1;
            c3 = p2 + Math.min(p3, cnt - (p1 + p2));
        }
    }
    
    return p1 == 0 && p2 == 0;
    

    }


  • 0
    F

    @joshua_al Hi joshua_al. Even though we have nested loops, the loop index i is increasing monotonically. Therefore each element in the array will be visited at most once, which means the time complexity will be O(n).


  • 0
    J

    @fun4LeetCode I see. Thanks for the explanation.


  • 0
    X

    So brilliant solution!!
    May I know how you can come up with this solution? Could you explain your mind process!! Thanks so much!


  • 0
    I

    One loop.

            int c1 = 0, c2 = 0, c3 = 0;
            for (int i = 1, j = 0; i <= nums.length; ++i) {
                if (i < nums.length && nums[i] == nums[i - 1]) continue;
                int repeats = i - j;
                if (repeats < c1 + c2) return false;
                c3 += c2;
                c2 = c1;
                c1 = Math.max(repeats - (c2 + c3), 0);
                c3 = repeats - c1 - c2;
                if (i == nums.length || nums[i] > nums[i - 1] + 1) {
                    if (c1 + c2 > 0) return false;
                    c3 = 0;
                }
                j = i;
            }
            return true;
    

  • 0
    J

    Great solution, upvoted. Can you share us your way of thinking?
    Because the key idea is your first statement. But that is really uneasy to came up with at the very beginning.


  • 3
    F

    @JadenPan @XiaoxingYu. Hi JadenPan and XiaoxingYu. The way I came up with this idea is as follows.

    First note that if the array can be split into consecutive subsequences of length >= 3, then every element in the array must belong to such a subsequence of length >= 3. So let's take any integer m in the array as an example. Apparently you can only add it to consecutive subsequences ending at m - 1. This tells you that we need information about consecutive subsequences ending at m - 1. But what kind of information about those subsequences are relevant here?

    First think about what distinguishes one subsequence from another. Since all the subsequences are ending at m - 1, they can only differ by length, i.e., each subsequence will be uniquely identified by its length. Now what if two subsequences have the same length? This suggests that we also need to keep track of the number of appearance of each length. Therefore in summary, we need to maintain information of subsequences ending at m - 1 with various lengths and their corresponding number of appearance.

    Of course I know we cannot keep track of all lengths, as this would require an infinite amount of memory. So the next question is to ponder more carefully the role that the length of each subsequence is playing here. From the point view of m - 1, we care more about subsequences of length 1 and 2. Since if there are no other elements that can extend these subsequences, we know the input array cannot be split into consecutive subsequences of length >= 3. On the other hand, we don't really care about subsequences of length >= 3, since they already meet the required condition. So I conclude that for subsequences ending at m - 1, there are really only three types are needed: those of length 1, of length 2 and of length >= 3.

    Once I figure this out, the next thing is to extend the conclusion to subsequences ending at m, so we can have a working recurrence relation. The key here is how we add m to those subsequences ending at m - 1. As I mentioned above, priorities should be given to those of length 1 and 2, since if these subsequences cannot be extended, the input array cannot be split into consecutive subsequences of length >= 3. After those subsequences are extended, if we have more elements of m, they can be used to extend subsequences ending at m - 1 with length >= 3. At last, if we still have elements of m, then they will form subsequences of length 1 since there are no more subsequences ending at m - 1 available for them. Therefore for subsequences ending at m, we still just need subsequences of length 1, length 2 and length >= 3. We can continue in this fashion until all elements are processed, at which point we need to check the number of subsequences of length 1 and 2 that ends at the last element of the input array to see if the input array can be split into consecutive subsequences of length >= 3 (since these subsequences cannot be extended as there are no more elements).

    Hope this helps!


  • 0
    B

    Nice code! Below is C++ version with slight tweaks:

        bool isPossible(vector<int>& nums) {
            if (nums.empty()) return true;
            
            int pre,cur=nums[0],c1=0,c2=0,c3,p1,p2,p3,cnt,i=0,n=nums.size();
            
            while (i<n) {
                pre=cur,cur=nums[i];
                cnt=0,p1=c1,p2=c2,p3=c3;
                
                while (i<n && nums[i]==cur) {
                    cnt++;
                    i++;
                }
                
                if (pre+1!=cur) {
                    if (p1!=0 || p2!=0) return false;
                    c1=cnt;
                    c2=0;
                    c3=0;
                } else {
                    if (cnt<p1+p2) return false;
                    c1=max(0,cnt-p1-p2-p3);
                    c2=p1;
                    c3=p2+min(p3,cnt-p1-p2);
                }
            }
            
            return c1==0 && c2==0;
        }
    

  • 0
    D

    Wow! What a solution! So efficient and boiled down to its essence! Also it can be easily generalized to cases where the length of each subsequence is > 3!


  • 0
    J

    @fun4LeetCode THX, truly appreciate.


  • 0
    Q

    How about this case
    [1,4,2,5,3,6,4,7,8]
    I think your solution is false, but it can split into:
    [1,2,3,4] and [4,5,6,7,8].


  • 0
    F

    @quheng Hi quheng. You test case is invalid. The input array should be sorted in ascending order.


  • 0
    X
    This post is deleted!

  • 0
    F

    Good solution!
    A little changes by C++ and beats 99.6%:

    class Solution {
    public:
        bool isPossible(vector<int>& nums) {
            int p1 = 0, p2 = 0, p3 = 0, c1 = 0, c2 = 0, c3 = 0, length = nums.size(), i, cnt = 0, cur = nums[0];
            for (i = -1; i < length - 1; ++cur, p1 = c1, p2 = c2, p3 = c3) {
                for (cnt = 0; i < length && nums[i + 1] == cur; ++i, ++cnt);
                if (cnt < p1 + p2) return false;
                c1 = max(0, cnt - (p1 + p2 + p3));
                c2 = p1;
                c3 = p2 + min(p3, cnt - (p1 + p2));
            }
            return p1 == 0 && p2 == 0;
        }
    };
    

  • 0
    D

    @fun4LeetCode
    Hi,

    I started with the understanding that the method isPossible() should return true if we can divide the sorted array into at least 2 subsequences having >= 3 numbers. My code is returning true for the array [1,2,5,5,6,6,7,8,8,9] but it is expected to be false.
    According to my understanding, the arr [1,2,5,5,6,6,7,8,8,9] could be divided into:
    [1,2,5,6,8,9]
    [5,6,7,8]
    So it should be true according to my understanding.
    Please help me out why isPossible() should return false for this scenario.


  • 0
    F

    @DebaratiMajumder Hi DebaratiMajumder. The problem description says "you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers". You test case cannot be split into subsequences of consecutive integers (therefore [1,2,5,6,8,9] is an invalid subsequence).


Log in to reply
 

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