LeetCode Solutions Blog

Split Array into Consecutive Subsequences

Number: 659

Difficulty: Medium

Paid? No

Problem Description

Given a sorted integer array nums, determine whether it is possible to split nums into one or more consecutive increasing subsequences, where each subsequence has a minimum length of 3. A valid consecutive subsequence means every number in the subsequence is exactly one more than its previous number.

Key Insights

Use a greedy approach to form the subsequences.
Utilize a frequency map to track how many times each number appears.
Use an additional map to track how many subsequences ending with a certain number need to be extended.
For each number, either extend an existing subsequence or start a new one if possible.
If neither is possible, then it is not possible to form valid subsequences.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in nums
Space Complexity: O(n) for storing the frequency and subsequence extension maps

Solution

We first count the frequency of every number in the array. Then, we iterate through the array and try to place each number:

If a number is already part of an existing subsequence (tracked via the extension map), then extend that subsequence.
Otherwise, check if the number can start a new subsequence (i.e., the next two consecutive numbers are available).
If neither condition holds, return false immediately. This greedy algorithm ensures that subsequences are extended whenever possible, helping to avoid wasteful starts of new subsequences that might block later extensions.

Code Solutions

# Python solution for splitting array into consecutive subsequences

from collections import Counter

def isPossible(nums):
    # Frequency map for all numbers in nums
    freq = Counter(nums)
    # Map to track the number of subsequences that can be extended (ending with a number)
    appendfreq = Counter()
    
    for num in nums:
        if freq[num] == 0:
            # This number has already been used completely, skip it
            continue
        
        # Decrement the frequency of current num as we are going to use it
        freq[num] -= 1
        
        if appendfreq[num] > 0:
            # If there's a subsequence ending with num-1, extend this subsequence with num
            appendfreq[num] -= 1
            # Now, this subsequence can be extended with num+1 in the future
            appendfreq[num + 1] += 1
        elif freq[num + 1] > 0 and freq[num + 2] > 0:
            # If num cannot extend a subsequence, try to create a new subsequence of length at least 3
            freq[num + 1] -= 1
            freq[num + 2] -= 1
            # The new subsequence now can be extended with num+3
            appendfreq[num + 3] += 1
        else:
            # Neither extending nor starting a new valid subsequence is possible
            return False
    return True

# Example usage:
print(isPossible([1,2,3,3,4,5]))  # Expected output: True