You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

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

class Solution {
    private class Sequence{
        int tail;
        int length;

        public Sequence(int tail, int length){
            this.tail = tail;
            this.length = length;
        }
    }
    public boolean isPossible(int[] nums) {

        if (nums == null || nums.length == 0) return true;

        PriorityQueue<Sequence> pq = new PriorityQueue<Sequence>(new Comparator<Sequence>(){
            public int compare(Sequence a, Sequence b){
                if (a.tail == b.tail){
                    return a.length - b.length;
                }
                return a.tail - b.tail;
            }
        });

        //[1,2,3,3,4,4,5,5]
        for (int num : nums){
            if (!pq.isEmpty() && pq.peek().tail == num){
                pq.offer(new Sequence(num, 1));
            }
            else{
                while (!pq.isEmpty() && num > pq.peek().tail + 1){
                    if (pq.poll().length < 3) return false;
                }

                if (pq.isEmpty()){
                    pq.offer(new Sequence(num, 1));
                }
                else{
                    Sequence seq = pq.poll();
                    seq.tail = num;
                    seq.length += 1;
                    pq.offer(seq);
                }
            }
        }

        while (!pq.isEmpty()){
            if (pq.poll().length < 3) return false;
        }

        return true;
    }
}

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> tail = new HashMap<>();

        for (int num : nums){
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        for (int num : nums){

            if (count.get(num) == 0) continue;
            else if (tail.getOrDefault(num, 0) > 0){
                count.put(num, count.get(num) - 1);
                tail.put(num, tail.getOrDefault(num, 0) - 1);
                tail.put(num + 1, tail.getOrDefault(num + 1, 0) + 1);
            }
            else if (count.getOrDefault(num + 1, 0) > 0 && count.getOrDefault(num + 2, 0) > 0){
                count.put(num, count.get(num) - 1);
                count.put(num + 1, count.get(num + 1) - 1);
                count.put(num + 2, count.get(num + 2) - 1);
                tail.put(num + 3, tail.getOrDefault(num + 3, 0) + 1);
            }
            else{
                return false;
            }
        }

        return true;
    }
}