Split Array into Consecutive Subsequences: Greedy Allocation

May 21, 20265 min read

leetcodeproblemmediumarrayshash-mapgreedy

LeetCode 659, Split Array into Consecutive Subsequences, asks whether you can split a sorted integer array into one or more subsequences where each subsequence consists of consecutive integers and has a length of at least 3. It looks like it might need backtracking, but a greedy approach with two hash maps handles it cleanly in a single pass.

The problem

You are given a sorted array of integers nums. Return true if you can split it into one or more subsequences such that each subsequence is made of consecutive integers and each subsequence has a length of at least 3.

For example, [1,2,3,3,4,5] can be split into [1,2,3] and [3,4,5], so the answer is true. But [1,2,3,3,4,4,5,5] can be split into [1,2,3,4,5] and [3,4,5], which also works. The array [1,2,3,4,4,5] cannot be split because after forming [1,2,3,4,5], the leftover 4 cannot form a valid subsequence on its own.

The sorted array [1,2,3,3,4,5] splits into two consecutive subsequences: [1,2,3] and [3,4,5]. Each has length 3 or more.

Why the greedy approach works

The key insight is that when you encounter a number, you have two choices: append it to an existing subsequence that is waiting for it, or start a brand new subsequence beginning with that number (which requires the next two numbers to also be available). The greedy rule is simple: always prefer extending an existing subsequence over starting a new one.

Why extend first? Because extending a subsequence costs nothing. The subsequence was already valid (or building toward validity), and adding to it only makes things better. Starting a new subsequence, on the other hand, is expensive. It consumes three numbers at once and creates a new obligation. By extending first, you leave more numbers available for future subsequences.

Think of it like seating guests at a table. If someone can join an existing table that has room, seat them there. Only open a new table when absolutely necessary, because opening a table requires at least three guests.

This greedy choice is locally optimal and leads to a globally optimal solution. If extending is possible but you choose to start a new subsequence instead, you waste resources that could have been used more flexibly later.

Step-by-step walkthrough

The algorithm uses two hash maps. The freq map counts how many of each number are still available. The need map tracks how many existing subsequences are waiting for a specific number as their next element.

For each number in the array:

If freq[num] is 0, skip it (already used).
If need[num] is greater than 0, extend an existing subsequence: decrement need[num], increment need[num+1].
Otherwise, check if freq[num+1] and freq[num+2] are both greater than 0. If so, start a new subsequence of length 3: decrement freq[num+1] and freq[num+2], increment need[num+3].
If neither option works, return false.

Step 1: Count the frequency of each number

The frequency map tells us how many of each number are available to place into subsequences.

Step 2: Initialize the need map (subsequences waiting for each number)

The need map tracks how many existing subsequences want a specific number as their next element. It starts empty.

Step 3: Process each number, greedy extend-or-start

For each number: if an existing subsequence needs it, extend that subsequence. Otherwise, start a new one using the next two consecutive numbers.

Step 4: All numbers placed successfully, return true

Every number was either used to extend an existing subsequence or to start a valid new one (length 3 or more). Result: true.

Practice this problem with spaced repetition

The code

from collections import Counter, defaultdict

def is_possible(nums):
    freq = Counter(nums)
    need = defaultdict(int)

    for num in nums:
        if freq[num] == 0:
            continue

        freq[num] -= 1

        if need[num] > 0:
            need[num] -= 1
            need[num + 1] += 1
        elif freq[num + 1] > 0 and freq[num + 2] > 0:
            freq[num + 1] -= 1
            freq[num + 2] -= 1
            need[num + 3] += 1
        else:
            return False

    return True

The solution iterates through the sorted array once. For each number, it first checks if the number has already been consumed (freq is 0). If not, it tries to extend an existing subsequence that needs this number. Failing that, it attempts to start a new subsequence of length 3 using the current number and the next two consecutive values. If neither option is available, no valid split exists.

A common mistake is forgetting to decrement freq[num] before checking the extend-or-start logic. If you skip that step, you will double-count numbers and produce incorrect results. Always consume the current number first, then decide where it goes.

Complexity analysis

Metric	Value
Time	O(n), single pass through the array
Space	O(n), for the frequency and need maps

Building the frequency map is O(n). The main loop processes each element once with O(1) hash map operations per element. The two maps together store at most O(n) entries.

Build your pattern library with CodeBricks

The building blocks

Greedy allocation with dual tracking

The core pattern here is maintaining two data structures that work in tandem: one tracks supply (what is available) and the other tracks demand (what is needed). Each decision consumes supply and may create new demand. This supply-and-demand framework appears in scheduling problems, resource allocation, and task assignment.

The template looks like this:

for item in items:
    if can_fulfill_existing_demand(item):
        fulfill(item)
    elif can_create_new_commitment(item):
        create(item)
    else:
        return False
return True

The "extend first, then start new" priority is what makes the greedy choice correct. You will see variations of this in problems where you must partition elements into groups that satisfy some constraint.

Edge cases

Before submitting, make sure your solution handles these:

Array of length 3 like [1,2,3]: one valid subsequence. Should return true.
Impossible split like [1,2,3,4,4,5]: after forming [1,2,3,4,5], the leftover 4 has no 5 or 6 to form a triple. Returns false.
Multiple subsequences like [1,2,3,3,4,4,5,5,6]: can be split into [1,2,3,4,5,6] and [3,4,5]. Returns true.
All same numbers like [1,1,1]: cannot form any consecutive subsequence of length 3. Returns false.
Long consecutive run like [1,2,3,4,5,6,7,8,9]: one big subsequence. Returns true.

The greedy solution handles all of these without special-case code because the freq and need maps naturally capture the constraints.

From understanding to recall

You have read the greedy allocation approach and it clicks. Two maps, one priority rule, one pass. But in an interview, the details matter. Which map do you check first? When do you decrement freq versus need? What gets incremented when you start a new subsequence?

These small decisions are easy to mix up under pressure if you have not practiced writing the solution from memory. Spaced repetition closes that gap. You write the dual-map greedy loop from scratch at increasing intervals until the pattern is automatic.

The supply-and-demand greedy framework is one of dozens of reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Group Anagrams - Another hash map problem where the data structure choice drives the entire solution
Gas Station - A greedy problem where a single pass with a reset rule replaces brute-force simulation
Non-overlapping Intervals - Greedy allocation applied to interval scheduling, same "extend or discard" thinking

CodeBricks breaks the split array problem into its greedy allocation and dual-map tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy partitioning question shows up in your interview, you do not think about it. You just write it.

Try CodeBricks free