659. Split Array into Consecutive Subsequences LeetCode Solution
In this guide, you will get 659. Split Array into Consecutive Subsequences LeetCode Solution with the best time and space complexity. The solution to Split Array into Consecutive Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
659. Split Array into Consecutive Subsequences LeetCode Solution in C++
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int, int> count;
vector<int> starts; // the start indices of each subsequence
vector<int> ends; // the end indices of each subsequence
for (const int num : nums)
++count[num];
for (int i = 0; i < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
const int num = nums[i];
const int currCount = count[num];
const int prevCount = count.contains(num - 1) ? count[num - 1] : 0;
const int nextCount = count.contains(num + 1) ? count[num + 1] : 0;
for (int j = 0; j < currCount - prevCount; ++j)
starts.push_back(num);
for (int j = 0; j < currCount - nextCount; ++j)
ends.push_back(num);
}
for (int i = 0; i < starts.size(); ++i)
if (ends[i] - starts[i] < 2)
return false;
return true;
}
}; /* code provided by PROGIEZ */
659. Split Array into Consecutive Subsequences LeetCode Solution in Java
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
List<Integer> starts = new ArrayList<>(); // the start indices of each subsequence
List<Integer> ends = new ArrayList<>(); // the end indices of each subsequence
for (final int num : nums)
count.merge(num, 1, Integer::sum);
for (int i = 0; i < nums.length; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
final int num = nums[i];
final int currCount = count.get(num);
final int prevCount = count.getOrDefault(num - 1, 0);
final int nextCount = count.getOrDefault(num + 1, 0);
for (int j = 0; j < currCount - prevCount; ++j)
starts.add(num);
for (int j = 0; j < currCount - nextCount; ++j)
ends.add(num);
}
for (int i = 0; i < starts.size(); ++i)
if (ends.get(i) - starts.get(i) < 2)
return false;
return true;
}
} // code provided by PROGIEZ
659. Split Array into Consecutive Subsequences LeetCode Solution in Python
