# Question

Formatted question description: https://leetcode.ca/all/659.html

 659. Split Array into Consecutive Subsequences

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


# Algorithm

https://leetcode.com/problems/split-array-into-consecutive-subsequences/solution/

# Code

•     class Solution {
public boolean isPossible(int[] nums) {
Integer prev = null;
int prevCount = 0;
int anchor = 0;
for (int i = 0; i < nums.length; ++i) {
int t = nums[i];
if (i == nums.length - 1 || nums[i+1] != t) {
int count = i - anchor + 1;
if (prev != null && t - prev != 1) {
while (prevCount-- > 0)
if (prev < starts.poll() + 2) return false;
prev = null;
}

if (prev == null || t - prev == 1) {
while (prevCount > count) {
prevCount--;
if (t-1 < starts.poll() + 2)
return false;
}
while (prevCount++ < count)
}
prev = t;
prevCount = count;
anchor = i+1;
}
}

while (prevCount-- > 0)
if (nums[nums.length - 1] < starts.poll() + 2)
return false;
return true;
}
}

############

class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();
for (int v : nums) {
if (d.containsKey(v - 1)) {
var q = d.get(v - 1);
d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(q.poll() + 1);
if (q.isEmpty()) {
d.remove(v - 1);
}
} else {
d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(1);
}
}
for (var v : d.values()) {
if (v.peek() < 3) {
return false;
}
}
return true;
}
}

• // OJ: https://leetcode.com/problems/split-array-into-consecutive-subsequences/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isPossible(vector<int>& nums) {
map<int, int> m;
for (int n : nums) m[n]++;
while (m.size()) {
auto i = m.begin();
int cnt = 0, len = 0, prev = i->first - 1;
while (i != m.end() && i->first == prev + 1 && i->second >= cnt) {
cnt = i->second;
prev = i->first;
if (!--i->second) i = m.erase(i);
else ++i;
++len;
}
if (len < 3) return false;
}
return true;
}
};

• class Solution:
def isPossible(self, nums: List[int]) -> bool:
d = defaultdict(list)
for v in nums:
if h := d[v - 1]:
heappush(d[v], heappop(h) + 1)
else:
heappush(d[v], 1)
return all(not v or v and v[0] > 2 for v in d.values())

############

class Solution(object):
def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
d = collections.defaultdict(list)
for num in nums:
if d[num - 1]:
heapq.heappush(d[num], heapq.heappop(d[num - 1]) + 1)
else:
heapq.heappush(d[num], 1)
return not any(length < 3 for length in sum(d.values(), []))


• func isPossible(nums []int) bool {
d := map[int]*hp{}
for _, v := range nums {
if d[v] == nil {
d[v] = new(hp)
}
if h := d[v-1]; h != nil {
heap.Push(d[v], heap.Pop(h).(int)+1)
if h.Len() == 0 {
delete(d, v-1)
}
} else {
heap.Push(d[v], 1)
}
}
for _, q := range d {
if q.IntSlice[0] < 3 {
return false
}
}
return true
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}

• class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
Map<Integer, Integer> endMap = new HashMap<Integer, Integer>();
for (int num : nums) {
int count = countMap.getOrDefault(num, 0) + 1;
countMap.put(num, count);
}
for (int num : nums) {
int count = countMap.getOrDefault(num, 0);
if (count > 0) {
int endCount = endMap.getOrDefault(num, 0);
if (endCount > 0) {
endMap.put(num, endCount - 1);
int nextCount = endMap.getOrDefault(num + 1, 0) + 1;
endMap.put(num + 1, nextCount);
} else {
int count1 = countMap.getOrDefault(num + 1, 0);
int count2 = countMap.getOrDefault(num + 2, 0);
if (count1 > 0 && count2 > 0) {
countMap.put(num + 1, count1 - 1);
countMap.put(num + 2, count2 - 1);
int endCount3 = endMap.getOrDefault(num + 3, 0) + 1;
endMap.put(num + 3, endCount3);
} else
return false;
}
countMap.put(num, count - 1);
}
}
return true;
}
}

############

class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();
for (int v : nums) {
if (d.containsKey(v - 1)) {
var q = d.get(v - 1);
d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(q.poll() + 1);
if (q.isEmpty()) {
d.remove(v - 1);
}
} else {
d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(1);
}
}
for (var v : d.values()) {
if (v.peek() < 3) {
return false;
}
}
return true;
}
}

• // OJ: https://leetcode.com/problems/split-array-into-consecutive-subsequences/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
bool isPossible(vector<int>& nums) {
map<int, int> m;
for (int n : nums) m[n]++;
while (m.size()) {
auto i = m.begin();
int cnt = 0, len = 0, prev = i->first - 1;
while (i != m.end() && i->first == prev + 1 && i->second >= cnt) {
cnt = i->second;
prev = i->first;
if (!--i->second) i = m.erase(i);
else ++i;
++len;
}
if (len < 3) return false;
}
return true;
}
};

• class Solution:
def isPossible(self, nums: List[int]) -> bool:
d = defaultdict(list)
for v in nums:
if h := d[v - 1]:
heappush(d[v], heappop(h) + 1)
else:
heappush(d[v], 1)
return all(not v or v and v[0] > 2 for v in d.values())

############

class Solution(object):
def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
d = collections.defaultdict(list)
for num in nums:
if d[num - 1]:
heapq.heappush(d[num], heapq.heappop(d[num - 1]) + 1)
else:
heapq.heappush(d[num], 1)
return not any(length < 3 for length in sum(d.values(), []))


• func isPossible(nums []int) bool {
d := map[int]*hp{}
for _, v := range nums {
if d[v] == nil {
d[v] = new(hp)
}
if h := d[v-1]; h != nil {
heap.Push(d[v], heap.Pop(h).(int)+1)
if h.Len() == 0 {
delete(d, v-1)
}
} else {
heap.Push(d[v], 1)
}
}
for _, q := range d {
if q.IntSlice[0] < 3 {
return false
}
}
return true
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}