LeetCode 659 - Split Array into Consecutive Subsequences

The problem gives us a sorted integer array nums, and asks whether we can divide every element into one or more subsequences that satisfy two conditions. First, each subsequence must consist of consecutive increasing integers.

leetcodemediumarrayhash-tablegreedyheap-(priority-queue)

LeetCode Problem 659

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us a sorted integer array nums, and asks whether we can divide every element into one or more subsequences that satisfy two conditions.

First, each subsequence must consist of consecutive increasing integers. This means every next value must be exactly 1 larger than the previous value. For example, [3,4,5] is valid, while [3,5,6] is not.

Second, every subsequence must have length at least 3. Short subsequences like [1,2] are invalid, even if they are consecutive.

The important detail is that every number in the array must belong to exactly one subsequence. We are not allowed to discard elements.

Because the input array is already sorted in non-decreasing order, we can process the numbers from left to right greedily. The sorted order is extremely important because consecutive subsequences naturally depend on processing smaller numbers before larger ones.

The constraints are relatively small, nums.length <= 10^4, but large enough that exponential or heavy backtracking solutions will not work efficiently. We need something close to linear time.

Several edge cases are important:

  • Duplicate numbers can appear many times, which means we may need to maintain multiple subsequences ending at the same value.
  • Some numbers may not be extendable into valid subsequences, especially near the end of the array.
  • A naive strategy that always starts new subsequences can fail because short unfinished subsequences may remain.
  • Arrays with fewer than three total elements are automatically impossible unless they are empty, which the constraints do not allow.

For example, [1,2,3,4,4,5] fails because one 4 can extend [1,2,3] into [1,2,3,4,5], but the second 4 cannot form a valid subsequence of length at least 3.

Approaches

Brute Force Approach

A brute-force solution would try all possible ways to assign each number to a subsequence. For every element, we could decide whether to append it to an existing subsequence or start a new one.

This approach is correct because it explores every possible partitioning of the array. Eventually, if a valid arrangement exists, the search would discover it.

However, the number of possible assignments grows exponentially. With duplicates and many branching choices, the recursion tree becomes enormous. Even moderate input sizes become infeasible.

For example, if several subsequences could legally accept the current number, brute force explores all of them independently. This leads to exponential time complexity.

Optimal Greedy Approach

The key observation is that extending an existing subsequence is always more important than starting a new one.

Suppose we already have a subsequence ending in x-1. When we encounter x, extending that subsequence is safer than creating a new subsequence starting at x. Why? Because short subsequences are dangerous. A subsequence of length 1 or 2 still needs future numbers to become valid.

If we unnecessarily start new subsequences, we may leave older subsequences stranded before reaching length 3.

This naturally leads to a greedy strategy:

  • Always try to extend an existing subsequence ending at num - 1.
  • Only start a new subsequence if extension is impossible.
  • When starting a new subsequence, immediately verify that num + 1 and num + 2 exist, because every subsequence must eventually reach length at least 3.

We maintain two hash maps:

  • frequency[num] tracks how many copies of each number remain unused.
  • subsequences[num] tracks how many subsequences currently end at num.

This allows efficient greedy decisions in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) or worse O(n) Tries all possible subsequence assignments
Optimal O(n) O(n) Greedily extends existing subsequences before creating new ones

Algorithm Walkthrough

  1. Count the frequency of every number in the array.

We use a hash map called frequency. This tells us how many unused copies of each value are still available.

For example:

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

frequency:
1 -> 1
2 -> 1
3 -> 2
4 -> 1
5 -> 1
  1. Create another hash map to track active subsequences.

We use subsequences[end] to represent how many subsequences currently end with the value end.

Initially, no subsequences exist. 3. Process the array from left to right.

Since the array is sorted, we always process smaller numbers before larger ones. 4. Skip numbers that have already been used.

If frequency[num] == 0, then all copies of this number have already been assigned to subsequences, so we continue. 5. Try to extend an existing subsequence ending at num - 1.

If subsequences[num - 1] > 0, then there exists a subsequence that can accept num.

We greedily extend it because extending old subsequences prevents them from becoming invalid short sequences.

Steps:

  • Decrease subsequences[num - 1]
  • Increase subsequences[num]
  • Decrease frequency[num]
  1. If extension is impossible, try to start a new subsequence.

To create a valid new subsequence, we must immediately reserve:

  • num
  • num + 1
  • num + 2

If any of these are unavailable, the answer is immediately false. 7. Create the new subsequence.

If all required numbers exist:

  • Decrease frequencies of num, num+1, and num+2
  • Record a subsequence ending at num+2
  1. If neither extension nor creation is possible, return false.

This means the current number cannot belong to any valid subsequence arrangement. 9. If all numbers are processed successfully, return true.

Why it works

The greedy invariant is that extending an existing subsequence is always safer than starting a new one. Existing subsequences may still be too short and require future numbers to become valid. If we ignore them and create new subsequences instead, we risk leaving unfinished sequences behind.

By always prioritizing extension, we minimize the number of unfinished subsequences and guarantee that every started subsequence can eventually reach length at least 3.

Python Solution

from collections import Counter, defaultdict
from typing import List

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        frequency = Counter(nums)
        subsequences = defaultdict(int)

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

            # Use current number to extend an existing subsequence
            if subsequences[num - 1] > 0:
                subsequences[num - 1] -= 1
                subsequences[num] += 1
                frequency[num] -= 1

            # Otherwise, try to create a new subsequence
            elif frequency[num + 1] > 0 and frequency[num + 2] > 0:
                frequency[num] -= 1
                frequency[num + 1] -= 1
                frequency[num + 2] -= 1

                subsequences[num + 2] += 1

            # Neither extending nor creating is possible
            else:
                return False

        return True

The implementation begins by counting how many copies of each number exist using Counter. This allows constant-time lookup of remaining unused values.

The subsequences map tracks how many subsequences end at each number. If subsequences[4] == 2, it means two subsequences currently end with 4 and could potentially be extended by a 5.

Inside the loop, we first skip numbers already consumed by previous operations.

The most important section is the greedy extension step. If a subsequence ending at num - 1 exists, we extend it immediately. This prevents short subsequences from being stranded.

If extension is impossible, we attempt to start a brand-new subsequence. However, we only do this if num + 1 and num + 2 are available. This guarantees the new subsequence will already satisfy the minimum length requirement.

If neither action is possible, the configuration is invalid, so we return False.

If the loop completes successfully, every number has been assigned to a valid subsequence.

Go Solution

func isPossible(nums []int) bool {
	frequency := make(map[int]int)
	subsequences := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	for _, num := range nums {
		if frequency[num] == 0 {
			continue
		}

		// Extend an existing subsequence
		if subsequences[num-1] > 0 {
			subsequences[num-1]--
			subsequences[num]++
			frequency[num]--

		// Create a new subsequence
		} else if frequency[num+1] > 0 && frequency[num+2] > 0 {
			frequency[num]--
			frequency[num+1]--
			frequency[num+2]--

			subsequences[num+2]++

		// Impossible to place current number
		} else {
			return false
		}
	}

	return true
}

The Go implementation closely mirrors the Python solution. Go maps return the zero value for missing keys, which is convenient because nonexistent entries automatically behave like frequency 0.

Unlike Python's defaultdict, Go does not require explicit initialization for missing keys. Accessing an absent key simply returns 0.

There are no integer overflow concerns because the constraints are small. Slices are used directly for iterating through the input array.

Worked Examples

Example 1

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

Initial state:

Number Frequency
1 1
2 1
3 2
4 1
5 1

Initial subsequences map is empty.

Iteration Trace

Current Num Action Subsequences State
1 Start new subsequence using 1,2,3 ends at 3: 1
2 Already used unchanged
3 One copy already used, one remains unchanged
3 Start new subsequence using 3,4,5 ends at 3: 1, ends at 5: 1
4 Already used unchanged
5 Already used unchanged

All numbers are assigned successfully, so the answer is true.

Valid subsequences:

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

Example 2

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

Iteration Trace

Current Num Action Subsequences State
1 Start new subsequence 1,2,3 ends at 3: 1
2 Already used unchanged
3 Try second copy unchanged
3 Start new subsequence 3,4,5 ends at 3: 1, ends at 5: 1
4 Extend subsequence ending at 3 ends at 4: 1, ends at 5: 1
4 Already used unchanged
5 Extend subsequence ending at 4 ends at 5: 2
5 Already used unchanged

Final subsequences:

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

Answer is true.

Example 3

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

Iteration Trace

Current Num Action Subsequences State
1 Start new subsequence 1,2,3 ends at 3: 1
2 Already used unchanged
3 Already used unchanged
4 Extend subsequence ending at 3 ends at 4: 1
4 Cannot extend and cannot create 4,5,6 failure

The second 4 cannot:

  • extend an existing subsequence ending at 3
  • create a new valid subsequence because 6 does not exist

Therefore the answer is false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each number is processed a constant number of times
Space O(n) Hash maps store frequencies and subsequence counts

The algorithm is linear because every operation on the hash maps is constant time on average, and each array element is visited once during processing.

The space complexity is linear because the frequency map and subsequence map may each contain up to n distinct keys in the worst case.

Test Cases

from typing import List
from collections import Counter, defaultdict

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        frequency = Counter(nums)
        subsequences = defaultdict(int)

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

            if subsequences[num - 1] > 0:
                subsequences[num - 1] -= 1
                subsequences[num] += 1
                frequency[num] -= 1

            elif frequency[num + 1] > 0 and frequency[num + 2] > 0:
                frequency[num] -= 1
                frequency[num + 1] -= 1
                frequency[num + 2] -= 1

                subsequences[num + 2] += 1

            else:
                return False

        return True

solution = Solution()

assert solution.isPossible([1,2,3,3,4,5]) == True  # basic valid split
assert solution.isPossible([1,2,3,3,4,4,5,5]) == True  # overlapping subsequences
assert solution.isPossible([1,2,3,4,4,5]) == False  # stranded number

assert solution.isPossible([1,2,3]) == True  # single valid subsequence
assert solution.isPossible([1,2]) == False  # too short

assert solution.isPossible([1,2,3,4,5,6]) == True  # one long subsequence
assert solution.isPossible([1,2,3,4,5,5,6,7]) == True  # extension plus new sequence

assert solution.isPossible([1,2,3,4,5,5,6]) == False  # cannot complete second sequence

assert solution.isPossible([1,1,2,2,3,3]) == True  # duplicate balanced counts
assert solution.isPossible([1,1,1,2,2,2,3,3,3]) == True  # multiple equal subsequences

assert solution.isPossible([1,2,3,4,6,7,8]) == True  # separate valid groups

assert solution.isPossible([-1,0,1,2,3,4]) == True  # negative numbers supported

assert solution.isPossible([1,2,3,4,5,6,7,8,9]) == True  # long continuous chain
Test Why
[1,2,3,3,4,5] Basic successful split
[1,2,3,3,4,4,5,5] Multiple overlapping subsequences
[1,2,3,4,4,5] Impossible due to stranded element
[1,2,3] Minimum valid subsequence
[1,2] Minimum invalid length
[1,2,3,4,5,6] Single long subsequence
[1,2,3,4,5,5,6,7] Mix of extension and new creation
[1,2,3,4,5,5,6] Incomplete second subsequence
[1,1,2,2,3,3] Balanced duplicates
[1,1,1,2,2,2,3,3,3] Multiple parallel subsequences
[-1,0,1,2,3,4] Negative values
[1,2,3,4,5,6,7,8,9] Long consecutive chain

Edge Cases

One important edge case is arrays that are too short to form valid subsequences. For example, [1,2] cannot possibly satisfy the minimum length requirement of 3. A naive implementation might incorrectly treat any consecutive sequence as valid. This implementation correctly rejects such cases because it only starts new subsequences when num+1 and num+2 both exist.

Another tricky edge case involves duplicate values. Consider [1,1,2,2,3,3]. A poor greedy strategy might place both 1s into the same subsequence attempt, leaving unmatched numbers later. The frequency map and subsequence tracking ensure that each copy is used independently and correctly distributed across multiple subsequences.

A third important edge case occurs when a number appears that can neither extend an existing subsequence nor start a new valid one. For example, in [1,2,3,4,4,5], the second 4 becomes stranded because no subsequence ends at 3, and 6 does not exist to create [4,5,6]. The implementation detects this immediately and returns False.

Another subtle edge case involves negative numbers. Since the problem allows values as small as -1000, the algorithm must not assume numbers are positive. Because the solution uses hash maps keyed by integers rather than array indexing, negative values are handled naturally without special logic.