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
3or 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] <= 1000numsis 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;
}
};
Input
Output
#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) {
pq.add(new int[]{num, num});
} else {
int[] subsequence = pq.poll();
pq.add(new int[]{subsequence[0], num});
}
}
while (!pq.isEmpty()) {
if (!isValidSubsequence(pq.poll())) {
return false;
}
}
return true;
}
private boolean isValidSubsequence(int[] subsequence) {
return subsequence[1] - subsequence[0] + 1 >= 3;
}
}
Input
Output
#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
}
Input
Output
#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
Input
Output