Last updated on January 10th, 2025 at 05:01 am
Here, we see a Split Array into Consecutive Subsequences LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Greedy, Heap
Companies
Level of Question
Medium
Split Array into Consecutive Subsequences LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Greedy Algorithm with Hash Maps”. The problem involves splitting the array into consecutive subsequences of at least length 3, and the greedy approach ensures that we extend existing subsequences whenever possible before starting new ones.
3. Code Implementation in Different Languages
3.1 Split Array into Consecutive Subsequences C++
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int,int> mp;
for(auto& it:nums)
mp[it]++;
for(auto& it:nums)
{
if(mp[it] == 0)
continue;
int freq = mp[it] , curr = it , count = 0;
while(mp.count(curr) && mp[curr] >= freq)
{
freq = fmax(freq,mp[curr]);
mp[curr]--;
count++;
curr++;
}
if(count < 3)
return false;
}
return true;
}
};
3.2 Split Array into Consecutive Subsequences Java
class Solution {
public boolean isPossible(int[] nums) {
HashMap<Integer,Integer> avaibilityMap = new HashMap<>();
HashMap<Integer,Integer> wantMap = new HashMap<>();
for(int i : nums){
avaibilityMap.put(i, avaibilityMap.getOrDefault(i,0)+1);
}
for(int i=0;i<nums.length;i++){
if(avaibilityMap.get(nums[i])<=0){
continue;
}
else if(wantMap.getOrDefault(nums[i],0)>0){
avaibilityMap.put(nums[i], avaibilityMap.getOrDefault(nums[i],0)-1);
wantMap.put(nums[i], wantMap.getOrDefault(nums[i],0)-1);
wantMap.put(nums[i]+1, wantMap.getOrDefault(nums[i]+1,0)+1);
}
else if(avaibilityMap.getOrDefault(nums[i],0)>0 && avaibilityMap.getOrDefault(nums[i]+1,0)>0 && avaibilityMap.getOrDefault(nums[i]+2,0)>0){
avaibilityMap.put(nums[i], avaibilityMap.getOrDefault(nums[i],0)-1);
avaibilityMap.put(nums[i]+1, avaibilityMap.getOrDefault(nums[i]+1,0)-1);
avaibilityMap.put(nums[i]+2, avaibilityMap.getOrDefault(nums[i]+2,0)-1);
wantMap.put(nums[i]+3, wantMap.getOrDefault(nums[i]+3,0)+1);
}
else{
return false;
}
}
return true;
}
}
3.3 Split Array into Consecutive Subsequences JavaScript
var isPossible = function(nums) {
if(nums.length < 3) return false;
const freqMap = new Map(), appendfreq = new Map();
nums.forEach(card => {
if (!freqMap.has(card))
freqMap.set(card, 0);
freqMap.set(card, freqMap.get(card) + 1);
});
for (let i of nums) {
if (freqMap.get(i) == 0) continue;
else if ((appendfreq.get(i) || 0) > 0) {
appendfreq.set(i, appendfreq.get(i) - 1);
appendfreq.set(i+1, (appendfreq.get(i+1) || 0) + 1);
}
else if ((freqMap.get(i+1) || 0) > 0 && (freqMap.get(i+2) || 0) > 0) {
freqMap.set(i+1, freqMap.get(i+1) - 1);
freqMap.set(i+2, freqMap.get(i+2) - 1);
appendfreq.set(i+3, (appendfreq.get(i+3) || 0) + 1);
}
else return false;
freqMap.set(i, freqMap.get(i) - 1);
}
return true;
};
3.4 Split Array into Consecutive Subsequences Python
class Solution(object):
def isPossible(self, nums):
seq = defaultdict(int)
left = Counter(nums)
for num in nums:
if (not left[num]): continue
if (seq[num-1] > 0):
seq[num-1] -= 1
seq[num] += 1
left[num] -= 1
else:
if (not left[num+1] or not left[num+2]):
return False
left[num] -= 1
left[num+1] -= 1
left[num+2] -= 1
seq[num+2] += 1
return True
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |