Split Array into Consecutive Subsequences
Problem 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
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] <= 1000
numsis sorted in non-decreasing order.
Solve it on LeetCode
Approaches
1. Greedy with Frequency and Append Maps
Intuition:
The task is to determine if we can split a given array into consecutive subsequences of length at least 3. The approach involves using two hash maps:
frequencymap to keep track of the remaining occurrences of each element.appendNeededmap to track the need to append an element to a previously formed subsequence.
The basic greedy strategy is:
- We iterate through the array and for each element
num: - First, check if
numcan be added to an existing subsequence where it can help form a valid consecutive sequence. - If
numcan't be added to any existing subsequence, try to start a new subsequence from it. - If neither is possible, we should return false because it is impossible to form the desired subsequences.
Steps:
- Use a
frequencymap to track the available counts of each number. - Use an
appendNeededmap to track if a number needs to be the next element in a subsequence. - Loop through each number
numin the input: - If the
frequencyofnumis zero, continue, meaning it's already used. - If
numcan be appended to a subsequence (i.e.,appendNeeded[num] > 0), reduce the need and increase the need for the next number. - If
numcan't be appended, try starting a new subsequencenum, num+1, num+2and update the necessary maps. - If neither appending to a subsequence nor starting one is possible, return false.
- If we can iterate through without issue, return true.
Code:
- Time Complexity: O(n), where n is the number of elements in the input array. Each element is processed a constant number of times.
- Space Complexity: O(n), as we use extra space for the frequency and appendNeeded maps.