659 - Split Array into Consecutive Subsequences

Difficulty: Medium | Pattern: Greedy + HashMap | Company tags: Google, Amazon

Problem Statement

You are given a sorted integer array nums. You want to split it into one or more subsequences where each subsequence consists of consecutive integers and has a length of at least 3.

Return true if you can split nums into such subsequences, otherwise return false.

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true  ([1,2,3] and [3,4,5])

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true  ([1,2,3,4,5] and [3,4,5])

Example 3:

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

Approach: Greedy — O(n), O(n)

Key insight: Use two counters:

• freq: count of each remaining number
• need: count of open subsequences that need the next number

For each number x:

1. If need[x] > 0: append to an existing subsequence. need[x] -= 1, need[x+1] += 1.
2. Else if freq[x] > 0 and freq[x+1] > 0 and freq[x+2] > 0: start a new subsequence. Decrement all three. need[x+3] += 1.
3. Else: return False.

from collections import Counter

def isPossible(nums: list[int]) -> bool:
    freq = Counter(nums)
    need = Counter()
    
    for x in nums:
        if freq[x] == 0:
            continue
        if need[x] > 0:
            need[x] -= 1
            need[x+1] += 1
            freq[x] -= 1
        elif freq[x] > 0 and freq[x+1] > 0 and freq[x+2] > 0:
            freq[x] -= 1
            freq[x+1] -= 1
            freq[x+2] -= 1
            need[x+3] += 1
        else:
            return False
    
    return True

Dry Run

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

freq: 1→1, 2→1, 3→2, 4→1, 5→1

x	action	need after
1	start new seq 1,2,3	need: 4→1; freq: 3→1,4→1,5→1
2	freq[2]=0, skip
3	freq[3]=0, skip
3	need[3]=0, try new seq 3,4,5	need: 4→0, 6→1
4	freq[4]=0, skip
5	freq[5]=0, skip

Return True ✓

Complexity

• Time: O(n)
• Space: O(n)