Split Array into Consecutive Subsequences

MediumHashing · Greedy🧩 Hashing & Counting LeetCode #659 ↗Updated Oct 30, 2026

Problem

You are given an integer array nums sorted in non-decreasing order. Decide whether every element can be assigned to exactly one subsequence such that each subsequence is a run of consecutive integers (each value one more than the previous) of length at least 3. Return true if such a split exists.

Inputnums = [1,2,3,3,4,5]Outputtrue ([1,2,3] and [3,4,5])

Inputnums = [1,2,3,3,4,4,5,5]Outputtrue ([1,2,3,4,5] and [3,4,5])

Inputnums = [1,2,3,4,4,5]Outputfalse

1 ≤ n ≤ 10⁴ · -1000 ≤ nums[i] ≤ 1000 · nums is sorted non-decreasing

Try it yourself

Java

class Solution {
    public boolean isPossible(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

For each value x (in order), extending an existing run that ends at x−1 is never worse than starting a new one. Only if no run is waiting must x start a fresh run — and then it must immediately grab x+1 and x+2.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceBacktracking over Assignments

Time ExponentialSpace O(n)

Process values in order. Each value either joins some run currently ending at x−1 or opens a new run; try every option recursively. Prune when a run shorter than 3 has an end below x−1, since it can never grow again.

Java

public boolean isPossible(int[] nums) {
    return assign(nums, 0, new ArrayList<>());
}

// each run is {lastValue, length}
private boolean assign(int[] nums, int i, List<int[]> runs) {
    int x = i < nums.length ? nums[i] : Integer.MAX_VALUE;
    for (int[] r : runs) {
        if (r[1] < 3 && r[0] < x - 1) return false; // dead short run
    }
    if (i == nums.length) return true;
    int size = runs.size(); // deeper calls may append, so iterate by index
    for (int k = 0; k < size; k++) {
        int[] r = runs.get(k);
        if (r[0] != x - 1) continue;
        r[0] = x; r[1]++;
        if (assign(nums, i + 1, runs)) return true;
        r[0] = x - 1; r[1]--; // undo
    }
    runs.add(new int[]{x, 1});
    if (assign(nums, i + 1, runs)) return true;
    runs.remove(runs.size() - 1);
    return false;
}

Explores every way to distribute duplicates — exponential, only for tiny inputs.

BetterMin-Heap of Runs (Extend the Shortest)

Time O(n log n)Space O(n)

Keep open runs in a heap ordered by end value, then by length. For each x, first close runs ending before x−1 (fail if any is shorter than 3). If the top run ends at x−1, extend it — it is the shortest such run, the one most in need. Otherwise start a new run.

Java

public boolean isPossible(int[] nums) {
    // {end, length}: smallest end first, then shortest
    PriorityQueue<int[]> runs = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    for (int x : nums) {
        while (!runs.isEmpty() && runs.peek()[0] < x - 1) {
            if (runs.poll()[1] < 3) return false; // closed too short
        }
        if (!runs.isEmpty() && runs.peek()[0] == x - 1) {
            int[] r = runs.poll();
            runs.add(new int[]{x, r[1] + 1});
        } else {
            runs.add(new int[]{x, 1});
        }
    }
    while (!runs.isEmpty()) {
        if (runs.poll()[1] < 3) return false;
    }
    return true;
}

Clear greedy with a provable choice, but pays log n per element.

OptimalCounts + “Runs Waiting for x” Map

Time O(n)Space O(n)

left[x] = unused copies of x; waiting[x] = runs (already length ≥ 3) whose next needed value is x. For each unused x: hand it to a waiting run if possible; otherwise open a run x, x+1, x+2 right away; if neither works, answer false.

Java

public boolean isPossible(int[] nums) {
    Map<Integer, Integer> left = new HashMap<>();
    Map<Integer, Integer> waiting = new HashMap<>(); // runs whose next value is key
    for (int x : nums) left.merge(x, 1, Integer::sum);

    for (int x : nums) {
        if (left.get(x) == 0) continue; // already used by an earlier run
        left.merge(x, -1, Integer::sum);
        if (waiting.getOrDefault(x, 0) > 0) {
            waiting.merge(x, -1, Integer::sum); // extend an existing run
            waiting.merge(x + 1, 1, Integer::sum);
        } else if (left.getOrDefault(x + 1, 0) > 0 && left.getOrDefault(x + 2, 0) > 0) {
            left.merge(x + 1, -1, Integer::sum); // open a new run x, x+1, x+2
            left.merge(x + 2, -1, Integer::sum);
            waiting.merge(x + 3, 1, Integer::sum);
        } else {
            return false;
        }
    }
    return true;
}

Dry runnums = [1,2,3,3,4,5]

i current index changed

i=0
1
i
2

3

4

4

5

open 1-2-3, wait[4]=1
i=1,2
1

2

3
i
4

4

5

already used → skip
i=3
1

2

3

4
i
4

5

extend run, wait[5]=1
i=4
1

2

3

4

4
i
5

no wait[4], no 6 → false

One pass with O(1) hash operations per element — linear time.

Pro tip

Opening a run grabs x+1 and x+2 immediately, so every run in waiting is already valid — no final length check is needed.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking over Assignments	`Exponential`	`O(n)`
Better	Min-Heap of Runs (Extend the Shortest)	`O(n log n)`	`O(n)`
Optimal	Counts + “Runs Waiting for x” Map	`O(n)`	`O(n)`

Common pitfalls

Preferring to start a new run over extending one — leaves short runs stranded.
Opening a run with just x and hoping to finish it later — check x+1, x+2 now.
Forgetting to skip values already consumed by an earlier run (count reaches 0).

Interview tips

Justify the greedy: extending never hurts because the extended run is already valid.
Mention the heap version first if you think of runs; then drop the heap via counts.
Walk through [1,2,3,4,4,5] to show a failing case clearly.

Pattern

Greedy with demand counts → group sorted items into chains; track how many chains are waiting for each next value.

My notes saved in this browser