Split Array into Consecutive Subsequences
Understanding the Problem
We need to partition every element in the sorted array into one or more groups, where each group forms a consecutive sequence of at least length 3. Every element must belong to exactly one group (since duplicates appear multiple times, each copy is assigned separately).
The difficulty is deciding where each element goes. When we reach a number like 4, we can use it to extend an existing subsequence that ends at 3, or start a new subsequence beginning at 4. A wrong choice early on can make it impossible to form valid subsequences later. For example, in [1,2,3,3,4,5], if we greedily build one long subsequence 1,2,3,4,5, we strand the second 3 by itself and the answer comes out false, even though splitting into [1,2,3] and [3,4,5] works.
Because the array is sorted, we process elements in increasing order, and when we reach a number, every smaller number has already been assigned. That lets us decide each element locally, without backtracking.
Key Constraints:
nums.length <= 10^4→ An O(n^2) solution passes, and O(n) or O(n log n) is comfortable.-1000 <= nums[i] <= 1000→ Values stay withinint, so there is no overflow concern, and counting with a hash map is cheap.numsis sorted → We can process elements left to right and make greedy decisions.
Approach 1: Track Every Subsequence in a List
Intuition
Build the subsequences directly. Keep a list of the open subsequences we have started so far, where each entry records the value the subsequence currently ends at and how long it is. Because the array is sorted, when we reach num, any subsequence that could accept it must end at exactly num - 1.
So for each num, we look for an open subsequence ending at num - 1 and append num to it. If several end at num - 1, we extend the shortest one, since the shortest subsequence is the one most at risk of finishing below length 3. If no subsequence ends at num - 1, we start a new one of length 1 ending at num. After all numbers are placed, the split is valid only if every subsequence reached length 3 or more.
Extending the shortest candidate first is what makes this correct. A subsequence that already has length 3 or more is safe no matter what happens next, so spending the new element on a still-short subsequence is never worse, and it protects the subsequence that has the most to lose.
Algorithm
- Keep a list
subs, where each entry is(endValue, length)for an open subsequence. - For each
numin the sorted array: - Scan
subsfor entries withendValue == num - 1and pick the one with the smallestlength. - If one is found, set its
endValuetonumand increment itslength. - Otherwise, add a new entry
(num, 1). - After processing every number, return true if every entry has
length >= 3, and false otherwise.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n numbers we scan the list of open subsequences to find the shortest one ending at num - 1, and that list can hold up to O(n) entries. For n <= 10^4 this still runs comfortably.
- Space Complexity: O(n). The list holds at most one entry per element when no extensions are possible.
The cost here comes from scanning the whole list of open subsequences for every element. The next approach removes that scan: instead of choosing which subsequence to extend, it tracks how many subsequences are waiting for each value, which lets each element be placed in O(1).
Approach 2: Greedy with Two Hash Maps
Intuition
We can avoid the scan in Approach 1 by not tracking each subsequence individually. For every number, there are two ways to place it:
- Extend an existing subsequence that ends at
num - 1by appendingnumto it. - Start a new subsequence beginning at
num, which requiresnum + 1andnum + 2to also be available.
Prefer extending over starting new. Extending an existing subsequence consumes only the current number, while starting a new one also reserves num + 1 and num + 2, future numbers that another subsequence might need. Extending therefore keeps more options open and never makes a previously satisfiable input fail.
We maintain two hash maps:
freq: how many copies of each number are still unassigned.tails: how many existing subsequences are waiting to be extended by a specific number. Iftails[5] = 2, two subsequences currently end at 4 and can take a 5 next.
Consider any valid split that instead starts a new subsequence at some num while an existing one ends at num - 1. Swapping the assignment, appending num to the existing subsequence and giving the new subsequence's num + 1 and num + 2 back to the pool, keeps both subsequences valid and frees two future numbers. So whenever extension is possible, choosing it can be turned into any valid solution without losing validity, which means the greedy choice never blocks a split that was otherwise achievable.
Algorithm
- Build a frequency map from the input array.
- Iterate through each number in the sorted array.
- If
freq[num] == 0, this copy was already used. Skip it. - If
tails[num] > 0, appendnumto an existing subsequence. Decrementtails[num], incrementtails[num + 1]. - Otherwise, try to start a new subsequence: check if
freq[num + 1] > 0andfreq[num + 2] > 0. If so, consume all three and settails[num + 3]++. - If neither option works, return false.
- If we process all elements successfully, return true.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array twice: once to build the frequency map, once to process each element. Each element is processed in O(1) time with hash map lookups.
- Space Complexity: O(n). The frequency map and tails map each store at most n entries.
The two-hash-map approach runs in O(n) and is the most practical of the three. It works because it never needs the individual lengths of subsequences: a subsequence becomes safe once it reaches length 3, and starting a new one always reserves three numbers up front, so no subsequence created by this method can ever finish too short. The final approach takes a different route, tracking each subsequence and its length explicitly with a heap, which makes the greedy choice from Approach 1 efficient.
Approach 3: Greedy with Min-Heap
Intuition
This is the list-based idea from Approach 1, made efficient. We still track each subsequence as (end_value, length), but we store the entries in a min-heap ordered first by end_value and then by length. For each num, the smallest entries are the ones ending earliest, so we can find and remove a subsequence ending at num - 1 in logarithmic time instead of scanning a list.
When several subsequences end at num - 1, the heap ordering by length means we extend the shortest first. A shorter subsequence is closer to violating the length-3 requirement, so giving it the current number first protects the subsequence with the least margin while leaving longer, already-safe subsequences alone.
After all numbers are placed, every subsequence remaining in the heap must have length 3 or more.
Algorithm
- Create a min-heap that orders entries by
(end_value, length). - For each number in the sorted array:
- Remove all heap entries where
end_value < num - 1(these subsequences can no longer be extended). If any of them have length < 3, return false. - If the heap has an entry with
end_value == num - 1, pop the one with the smallest length, extend it to(num, length + 1), and push it back. - Otherwise, push a new entry
(num, 1). - After processing all elements, check that every remaining entry in the heap has length >= 3.
Example Walkthrough
Code
- Time Complexity: O(n log n). Each element triggers at most one push and one pop on the heap, each costing O(log n). The cleanup loop across all iterations removes at most n total entries, so it's O(n log n) overall.
- Space Complexity: O(n). The heap stores at most n entries (one per element in the worst case).