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

• 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;
}
``````

• 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.

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;
``````

}

• @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)`.

• @fun4LeetCode I see. Thanks for the explanation.

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

• 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;
``````

• 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.

• @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!

• 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;
}
``````

• 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!

• @fun4LeetCode THX, truly appreciate.

[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].

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

• This post is deleted!

• 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;
}
};
``````

• 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.
• @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).