MediumArrayHash TableGreedyHeap (Priority Queue)

Split Array into Consecutive Subsequences

1 approach, code in every language

You are given an integer array that is sorted in non-decreasing order. Decide whether it is possible to partition all of its elements into one or more subsequences, where each subsequence is a run of consecutive increasing integers.

Every subsequence must have a length of at least three. Return true if such a partition exists and false otherwise.

Example 1

Input: nums = [1,2,3,3,4,5]

Output: true

The array splits into [1,2,3] and [3,4,5], each a consecutive run of length 3.

Example 2

Input: nums = [1,2,3,4,4,5]

Output: false

No valid split exists: any attempt leaves a leftover run shorter than three consecutive integers.

Constraints

1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000
nums is sorted in non-decreasing order.

Greedy with Frequency and Need Maps

Prefer extending an existing subsequence over starting a new one, tracking how many runs currently need each value to continue.

Loading animation…

Intuition

Process numbers in ascending order and keep two counters: freq[v] for how many copies of v are still unused, and need[v] for how many already-formed subsequences are waiting for value v to extend. When we reach a value v, the greedy rule is to first spend it extending a subsequence that needs it, because appending to an existing run is never worse than opening a new one. If nothing needs v, we try to start a brand-new run v, v+1, v+2, which requires those next two values to be available. If neither option is possible, a valid partition cannot exist. Consuming everything successfully means every run reached length three or more.

Algorithm walkthrough

1Count the frequency of every value into a freq map and start need empty.
2Iterate through the numbers in order; skip any value whose freq has already been fully consumed.
3If need[v] is positive, attach v to a waiting run: decrement need[v] and increment need[v+1].
4Otherwise, if freq[v+1] and freq[v+2] are both available, open a new run by consuming those two and setting need[v+3] up by one.
5If neither branch applies, return false immediately.
6Decrement freq[v] after placing it, and return true once all numbers are placed.

Implementation

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        freq = Counter(nums)
        need = Counter()
        for num in nums:
            if freq[num] == 0:
                continue
            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
            freq[num] -= 1
        return True

Time

O(n)

Space

O(n)

A single frequency pass plus a single greedy pass, each map operation averaging O(1). The maps store at most one entry per distinct value.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free