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:

cur != pre + 1
: for this case,cur
cannot be added to any consecutive subsequences ending atpre
, therefore, we must havep1 == 0 && p2 == 0
; otherwise the input array cannot be split into consecutive subsequences of length>= 3
. Now letc1, c2, c3
be the number of consecutive subsequences ending atcur
with length of1
, length of2
and length>= 3
, respectively, we will havec1 = cnt, c2 = 0, c3 = 0
, which means we only have consecutive subsequence ending atcur
with length of1
and its number given bycnt
. 
cur == pre + 1
: for this case,cur
can be added to consecutive subsequences ending atpre
and thus extend those subsequences. But priorities should be given to those with length of1
first, then length of2
and lastly length>= 3
. Also we must havecnt >= p1 + p2
; otherwise the input array cannot be split into consecutive subsequences of length>= 3
. Again letc1, c2, c3
be the number of consecutive subsequences ending atcur
with length of1
, length of2
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 addingcur
to the end of subsequences of length1
will make them subsequences of length2
, and we havep1
such subsequences, thereforec2 = p1
. Then addingcur
to the end of subsequences of length2
will make them subsequences of length3
, and we havep2
such subsequences, thereforec3
is at leastp2
. Ifcnt > p1 + p2
, we can add the remainingcur
to the end of subsequences of length>= 3
to make them even longer subsequences. The number of such subsequences is the smaller one ofp3
andcnt  (p1 + p2)
. In total,c3 = p2 + min(p3, cnt  (p1 + p2))
. Ifcnt > p1 + p2 + p3
, then we still have remainingcur
that cannot be added to any subsequences. These residuecur
will form subsequences of length1
, hencec1 = 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;
}