Split Array into Consecutive Subsequences

Problem Description

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.

Key Insights

• The input array is sorted, which simplifies the process of finding consecutive sequences.
• We need to keep track of how many subsequences can be formed and the current lengths of these subsequences.
• A greedy approach can be used to build these subsequences by always trying to extend the existing ones before starting new ones.
• We can utilize a hash map to efficiently manage and count the frequency of occurrences of each number.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use a hash map to count the frequency of each number in the input array. We will then attempt to build subsequences using a greedy approach:

1. Iterate through the numbers in the array.
2. For each number, check if it can be appended to an existing subsequence (i.e., if there is a subsequence ending with num-1).
3. If it can, append it to that subsequence; if not, check if it can start a new subsequence (i.e., if there are at least two subsequent numbers available).
4. If neither option is available, return false.

This approach ensures that all subsequences are of valid lengths and that they are consecutive.

Code Solutions