659. Split Array into Consecutive Subsequences

Description

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.

Solutions

• 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;
}
}

• class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d;
for (int v : nums) {
if (d.count(v - 1)) {
auto& q = d[v - 1];
d[v].push(q.top() + 1);
q.pop();
if (q.empty()) {
d.erase(v - 1);
}
} else {
d[v].push(1);
}
}
for (auto& [_, v] : d) {
if (v.top() < 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())


• 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 any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}