LeetCode 659: Split Array into Consecutive Subsequences

Problem Description

LeetCode Problem 659

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

• Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
• All subsequences have a length of 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] —> 1, 2, 3
[1,2,3,3,4,5] —> 3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] —> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] —> 3, 4, 5

Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

Constraints:

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000
• nums is sorted in non-decreasing order.

Difficulty: Medium

Tags: array, hash table, greedy, heap (priority queue)

Rating: 84.65%

Solution Approach

The key insight is that when we encounter a number, we have two choices:

1. Use it to extend an existing sequence that ends with the previous number
2. Start a new sequence of length 3 beginning with this number

My solution uses a greedy approach with two main data structures:

• A counter to track available numbers
• A hash map to track how many sequences end at each number

Solution

Here’s my Python solution to this problem:

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        counts = Counter(nums)
        print(counts)

        # Track how many sequences end at each number
        end = {} 

        for n in nums:
            # Skip if number is already used up
            if counts[n] == 0:
                continue
            
            # Try appending in existing sequence
            if n in end and end[n] > 0:
                end[n] -= 1
                end[n+1] = end.get(n+1, 0) + 1

            # Try starting a new sequence of length 3
            elif counts.get(n+1, 0) > 0 and counts.get(n+2, 0) > 0:
                counts[n+1] -= 1
                counts[n+2] -= 1
                end[n+3] = end.get(n+3, 0) + 1

            else:
                return False
            
            counts[n] -= 1
        
        return True

Example Walkthrough

Let’s see how this works with the input [1,2,3,3,4,5]:

1. Initially:
   • counts = {1:1, 2:1, 3:2, 4:1, 5:1}
   • end = {}
2. Processing 1:
   • Can’t append (no existing sequences)
   • Can start new sequence [1,2,3]
   • Update: counts = {1:0, 2:0, 3:1, 4:1, 5:1}, end = {4:1}
3. Processing remaining numbers:
   • The second 3 starts new sequence [3,4,5]
   • All numbers get used in valid sequences

Complexity Analysis

The solution has the following complexity characteristics:

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

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.