LeetCode [659] Split Array into Consecutive Subsequences

 659. Split Array into Consecutive Subsequences

Medium

Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

 

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]
Output: False

 

Constraints:

• 1 <= nums.length <= 10000

class Solution {
    public boolean isPossible(int[] nums) {
        int n = nums.length;
        if(n<3) return false;
        int i = 0;
        while(i<n&&nums[i]==nums[0]) i++;
        int cnt = i;//count of repeated number
        int prev = nums[0];
        int p1 = cnt, p2=0, p3=0;

        while(i<n){
            int cur = nums[i++];
            cnt = 1;
            while(i<n && nums[i]==cur){
                cnt++;
                i++;
            }
            if(cur==prev+1){
                if(p1+p2>cnt) return false;
                int c2 = p1, c3 = p2+Math.min(p3, cnt-p1-p2), c1 = Math.max(0, cnt-p1-p2-p3);
                p1=c1;
                p2=c2;
                p3=c3;
            }else{
                if(p1+p2>0) return false;
                p1=0;
                p2=0;
                p3=cnt;
            }
            prev = cur;
        }
        return p1+p2==0;
    }
}