## Algorithm

Problem Name: 659. Split Array into Consecutive Subsequences

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

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] --> 1, 2, 3
[1,2,3,3,4,5] --> 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] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 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.
```

Constraints:

• `1 <= nums.length <= 104`
• `-1000 <= nums[i] <= 1000`
• `nums` is sorted in non-decreasing order.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map < int, int>m, f;
for(auto x: nums) m[x]++;
for(auto x: nums){
if(!m[x]) continue;
else if(f[x]){
f[x]--;
f[x + 1]++;
}
else if(m[x + 1] && m[x + 2]){
m[x + 1]--;
m[x + 2]--;
f[x + 3]++;
}
else return false;
m[x]--;
}
return true;
}
};

class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map < int, int>m, t;
for (int& x: nums) {
++m[x];
}

for (int& x: nums) {
if (!m[x]) {
continue;
}
--m[x];
if (t[x]) {
--t[x];
++t[x + 1];
} else if (m[x + 1] && m[x + 2]) {
--m[x + 1];
--m[x + 2];
++t[x + 3];
} else {
return false;
}
}
return true;
}
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3,3,4,5]

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean isPossible(int[] nums) {
PriorityQueue<int[]> pq = new PriorityQueue<>((int[] o1, int[] o2) -> {
if (o1[1] == o2[1]) {
return (o1[1] - o1[0]) - (o2[1] - o2[0]);
}
return o1[1] - o2[1];
});
for (int num : nums) {
while (!pq.isEmpty() && pq.peek()[1] + 1  <  num) {
if (!isValidSubsequence(pq.poll())) {
return false;
}
}
if (pq.isEmpty() || pq.peek()[1] == num) {
} else {
int[] subsequence = pq.poll();
}
}
while (!pq.isEmpty()) {
if (!isValidSubsequence(pq.poll())) {
return false;
}
}
return true;
}

private boolean isValidSubsequence(int[] subsequence) {
return subsequence[1] - subsequence[0] + 1 >= 3;
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,3,4,5]

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const isPossible = function(nums) {
const freq = new Map()
const build = new Map()
for (let el of nums) {
freq.has(el) ? freq.set(el, freq.get(el) + 1) : freq.set(el, 1)
}
for (let item of nums) {
if (freq.get(item) === 0) continue
else if (getOrDefault(build, item) > 0) {
build.set(item, build.get(item) - 1)
build.set(item + 1, getOrDefault(build, item + 1) + 1)
} else if (getOrDefault(freq, item + 1) > 0 && getOrDefault(freq, item + 2) > 0) {
freq.set(item + 1, freq.get(item + 1) - 1)
freq.set(item + 2, freq.get(item + 2) - 1)
build.set(item + 3, getOrDefault(build, item + 3) + 1)
} else return false
freq.set(item, freq.get(item) - 1)
}
return true
}

function getOrDefault(map, key) {
return map.get(key) || 0
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,3,4,4,5,5]

Output

cmd
true

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def isPossible(self, nums):
heap, last = [], collections.defaultdict(int)
for num in nums:
last[num] += 1
if heap and heap[0][0] <= num - 1:
if heap[0][0] < num - 1:
return False
else:
last[num - 1] -= 1
n, l = heapq.heappop(heap)
if l == -1:
heapq.heappush(heap, (num, -2))
elif num - 1 not in last or not last[num - 1]:
heapq.heappush(heap, (num, -1))
else:
last[num - 1] -= 1
return not heap
``````
Copy The Code &

Input

cmd
nums = [1,2,3,3,4,4,5,5]

Output

cmd
true