AlgoMaster Logo

Split Array into Consecutive Subsequences

Last Updated: March 21, 2026

medium
5 min read

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 key challenge is deciding where each element should go. When we encounter a number like 4, should we use it to extend an existing subsequence that ends at 3, or should we start a brand new subsequence beginning at 4? This decision matters because a greedy wrong choice early on can make it impossible to form valid subsequences later.

The fact that the array is sorted is a huge advantage. It means we process elements in order, and when we encounter a number, all smaller numbers have already been assigned. This lets us make local decisions without backtracking.

Key Constraints:

  • nums.length <= 10^4 → An O(n^2) solution is fine, and O(n) is ideal. Even O(n log n) is very comfortable.
  • -1000 <= nums[i] <= 1000 → The value range is small (2001 possible values), so frequency counting with a hash map is cheap.
  • nums is sorted → We can process elements left to right and make greedy decisions.

Approach 1: Brute Force (Simulation)

Intuition

The most direct approach is to simulate the process. Repeatedly scan through the available elements and try to build consecutive subsequences of length 3 or more. Each time we successfully extract a valid subsequence, we remove those elements and repeat. If at any point we can't form a new valid subsequence but elements remain, we return false.

To track available elements, we use a frequency map. Starting from the smallest available number, we greedily extend the subsequence as far as possible, then check if its length is at least 3.

Algorithm

  1. Build a frequency map counting occurrences of each number.
  2. While elements remain in the frequency map:
    • Find the smallest number with a positive count.
    • Starting from that number, greedily extend a consecutive subsequence (decrementing counts as we go).
    • If the subsequence length is less than 3, return false.
  3. If all elements are consumed in valid subsequences, return true.

Example Walkthrough

1Initial: freq = {1:1, 2:1, 3:2, 4:1, 5:1}
0
1
1
2
2
3
3
3
4
4
5
5
1/5

Code

The bottleneck here is that we repeatedly scan the entire frequency map to find the smallest element and build one subsequence at a time. What if we could process each element exactly once and decide on the spot where it belongs?

Approach 2: Greedy with Two Hash Maps

Intuition

Instead of repeatedly scanning and extracting subsequences, we can process each element exactly once from left to right. The key insight is this: for every number, we have two options.

  1. Extend an existing subsequence that ends at num - 1 by appending num to it.
  2. Start a new subsequence beginning at num, which requires num + 1 and num + 2 to also be available.

The greedy choice is to always prefer option 1 (extending) over option 2 (starting new). Why? Because extending an existing subsequence never hurts. That subsequence already needs to reach length 3, and making it longer only helps. Starting a new subsequence, on the other hand, creates a new obligation: we now need two more consecutive numbers just to make it valid.

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. If tails[5] = 2, it means there are 2 subsequences whose last element is 4, and they'd happily accept a 5.

Algorithm

  1. Build a frequency map from the input array.
  2. Iterate through each number in the sorted array.
  3. If freq[num] == 0, this copy was already used. Skip it.
  4. If tails[num] > 0, append num to an existing subsequence. Decrement tails[num], increment tails[num + 1].
  5. Otherwise, try to start a new subsequence: check if freq[num + 1] > 0 and freq[num + 2] > 0. If so, consume all three and set tails[num + 3]++.
  6. If neither option works, return false.
  7. If we process all elements successfully, return true.

Example Walkthrough

1Initial: freq={1:1, 2:1, 3:2, 4:1, 5:1}, tails={}
0
1
1
2
2
3
3
3
4
4
5
5
1/6

Code

The two-hash-map approach is already O(n) and is the most practical solution for interviews. But it only tracks how many subsequences end at each value, not their individual lengths. What if we used a data structure that tracked each subsequence individually?

Approach 3: Greedy with Min-Heap

Intuition

Instead of just counting how many subsequences end at each value, we can track each subsequence explicitly using a min-heap (priority queue). For each value in the array, the heap stores entries of the form (end_value, length). When we process a new number, we look for the shortest subsequence ending at num - 1 and extend it. If no such subsequence exists, we start a new one.

Why the shortest? Because shorter subsequences are in more danger of being invalid (length < 3). By extending the shortest one first, we give it the best chance of reaching length 3. This is another instance of the greedy principle: help the most desperate subsequence first.

At the end, we check if every subsequence in the heap has length >= 3.

Algorithm

  1. Create a min-heap that orders entries by (end_value, length).
  2. 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).
  3. After processing all elements, check that every remaining entry in the heap has length >= 3.

Example Walkthrough

1Heap=[]. num=1: no entry ends at 0. Start new → push (1,1)
0
1
num
1
2
2
3
3
3
4
4
5
5
1/7

Code