You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:


	Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
	All subsequences have a length of 3 or more.


Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

&nbsp;
Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --&gt; 1, 2, 3
[1,2,3,3,4,5] --&gt; 3, 4, 5


Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --&gt; 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --&gt; 3, 4, 5


Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 104
	-1000 &lt;= nums[i] &lt;= 1000
	nums is sorted in non-decreasing order.


class Solution:

    from collections import defaultdict

    def isPossible(self, nums):
        # If the length of the array is less than 3, it's not possible to create subsequences of length 3 or more.
        if len(nums) < 3:
            return False

        # 'count' dictionary stores the frequency of each number in the input array.
        count = defaultdict(int)

        # 'tails' dictionary stores the number of subsequences that end at a certain number.
        tails = defaultdict(int)

        # Populate the 'count' dictionary with the frequency of each number.
        for num in nums:
            count[num] += 1

        # Iterate through the input array.
        for num in nums:
            # If the count of the current number is 0, it means this number has already been used in a subsequence.
            if count[num] == 0:
                continue
            # If there is a subsequence that ends with the current number minus 1,
            # it means we can extend that subsequence by adding the current number.
            elif tails[num - 1] > 0:
                tails[num - 1] -= 1  # Decrease the count of the tails that end with the current number minus 1.
                tails[num] += 1  # Increase the count of the tails that end with the current number.
            # If there are enough numbers after the current number to form a subsequence,
            # create a new subsequence starting with the current number.
            elif count[num + 1] > 0 and count[num + 2] > 0:
                count[num + 1] -= 1  # Decrease the count of the next number.
                count[num + 2] -= 1  # Decrease the count of the number after the next number.
                tails[num + 2] += 1  # Increase the count of the tails that end with the number after the next number.
            else:
                # If we can't extend an existing subsequence or start a new one, return False.
                return False

            # Decrease the count of the current number since it's used in a subsequence.
            count[num] -= 1

        # If the function successfully iterates through the entire array, return True.
        return True
class Solution {
  public boolean isPossible(int[] nums) {
    int[] freq = new int[2002], subEnd = new int[2002];
    for (int i : nums) {
      int num = i + 1001;
      freq[num]++;
    }
    for (int i : nums) {
      int num = i + 1001;
      if (freq[num] == 0) continue; // Num already in use
      freq[num]--;
      if (subEnd[num - 1] > 0) { // Put into existing subsequence
        subEnd[num - 1]--;
        subEnd[num]++;
      }
      // New subsequence of size 3 is possible
      else if (freq[num + 1] > 0 && freq[num + 2] > 0) {
        freq[num + 1]--;
        freq[num + 2]--;
        subEnd[num + 2]++; // New subsequence
      } else return false;
    }
    return true;
  }
}
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> pq;
        unordered_map<int, int> um;
        for(int &num : nums)
        {
            pq.push(num);
            um[num]++;
        }
        queue<int> q;
        int count = 0, prev;
        while(!pq.empty())
        {
            if(count == 0)
            {
                prev = pq.top();
                pq.pop();
                count++;
            }
            else if(pq.top() == prev+1)
            {
                if(um[pq.top()] >= um[prev])
                {
                    um[prev]--;
                    pq.pop();
                    prev += 1;
                    count++;
                }
                else if(um[pq.top()] < um[prev])
                {
                    um[prev]--;
                    if(count <= 2) return false;
                    while(!q.empty())
                    {
                        pq.push(q.front());
                        q.pop();
                    }
                    count = 0;
                }
            }
            else if(pq.top() == prev)
            {
                q.push(pq.top());
                pq.pop();
                if(pq.empty())
                {
                    if(count <= 2) return false;
                    while(!q.empty())
                    {
                        pq.push(q.front());
                        q.pop();
                    }
                    count = 0;
                }
            }
            else if(pq.top() > prev+1)
            {
                if(count <= 2) return false;

                while(!q.empty())
                {
                    pq.push(q.front());
                    q.pop();
                }
                count = 0;
            }
        }
        if(count > 0 && count <= 2) return false;
        return true;
    }
};
var isPossible = function(nums) {
	const need = new Map();
	const hash = nums.reduce((map, num) => {
		const count = map.get(num) ?? 0;
		map.set(num, count + 1);
		return map;
	}, new Map());

	for (const num of nums) {
		const current = hash.get(num);
		if (current === 0) continue;

		const currentNeed = need.get(num);
		const next1 = hash.get(num + 1);
		const next2 = hash.get(num + 2);
		if (currentNeed > 0) {
			const need1 = need.get(num + 1) ?? 0;
			need.set(num, currentNeed - 1);
			need.set(num + 1, need1 + 1);
		} else if (next1 > 0 && next2 > 0) {
			const need3 = need.get(num + 3) ?? 0;
			hash.set(num + 1, next1 - 1);
			hash.set(num + 2, next2 - 1);
			need.set(num + 3, need3 + 1);
		} else {
			return false;
		}
		hash.set(num, current - 1);
	}
	return true;
};
Split Array into Consecutive Subsequences