LeetCode 659: Split Array into Consecutive Subsequences Solution in Python – A Step-by-Step Guide

What Is LeetCode 659: Split Array into Consecutive Subsequences?

In LeetCode 659: Split Array into Consecutive Subsequences, you’re given an integer array nums (not necessarily sorted), and your task is to determine if it can be split into one or more subsequences where each subsequence:

• Contains at least three consecutive integers (e.g., [1, 2, 3]).
• Uses all elements of the array exactly once.

Return True if possible, False otherwise. For example, with nums = [1, 2, 3, 3, 4, 5], you can split into [1, 2, 3] and [3, 4, 5], so it’s True. With nums = [1, 2, 3, 4], no split into sequences of length ≥ 3 works, so it’s False. This problem tests your ability to partition an array into consecutive runs efficiently.

Problem Statement

• Input:
• nums: List of integers.
• Output: A boolean—True if split is possible, False otherwise.
• Rules:
• Split into subsequences of ≥ 3 consecutive integers.
• Use all elements exactly once.
• Subsequences need not be contiguous in original array.

Constraints

• 1 ≤ nums.length ≤ 10⁴.
• -10⁹ ≤ nums[i] ≤ 10⁹.

Examples

• Input: nums = [1, 2, 3, 3, 4, 5]
• Output: True (Split: [1, 2, 3], [3, 4, 5])
• Input: nums = [1, 2, 3, 4]
• Output: False (No split into ≥ 3 consecutive possible)
• Input: nums = [1, 2, 3, 3, 4, 4, 5, 5]
• Output: True (Split: [1, 2, 3], [3, 4, 5], [4, 5])

These examples set the array—let’s solve it!

Understanding the Problem: Splitting into Sequences

To solve LeetCode 659: Split Array into Consecutive Subsequences in Python, we need to check if nums can be partitioned into subsequences of at least three consecutive integers, using all elements. A brute-force approach—trying all possible splits—would be O(2^n), impractical for n ≤ 10⁴. Since we’re building consecutive sequences, we can use frequency tracking or state transitions. We’ll explore:

• Best Solution (Greedy with Hash Maps): O(n) time, O(n) space—fast and intuitive.
• Alternative Solution (Dynamic Programming): O(n²) time, O(n) space—systematic but slower.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Hash Maps

Why This Is the Best Solution

The greedy with hash maps approach is the top choice for LeetCode 659 because it’s efficient—O(n) time with O(n) space—and uses a greedy strategy to extend or start new sequences by tracking frequencies and sequence ends, ensuring minimal length requirements. It fits constraints (n ≤ 10⁴) perfectly and is straightforward once you see the hash map magic. It’s like greedily stitching numbers into sequences as you go!

How It Works

Think of this as a sequence stitcher:

• Step 1: Count Frequencies:
• Use a hash map freq to count occurrences of each number.
• Step 2: Track Sequence Ends:
• Use a hash map tails to count sequences ending at each number.
• Step 3: Greedy Assignment:
• For each number num in sorted order:
• If freq[num] > 0:
• Extend existing sequence: If tails[num-1] > 0, use one, add to tails[num].
• Start new sequence: If freq[num+1] > 0 and freq[num+2] > 0, use all three.
• Else, return False (can’t form ≥ 3).
• Step 4: Return Result:
• Return True if all numbers used.

It’s like a sequence grower—extend or start!

Step-by-Step Example

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

• Step 1: freq = {1: 1, 2: 1, 3: 2, 4: 1, 5: 1}.
• Step 2: tails = {}.
• Step 3: Process sorted numbers:
• 1: freq[1]=1, no tail at 0, start [1, 2, 3], freq[1]--, freq[2]--, freq[3]--, tails[3]=1.
• freq = {1: 0, 2: 0, 3: 1, 4: 1, 5: 1}, tails = {3: 1}.
• 2: freq[2]=0, skip.
• 3: freq[3]=1, tails[2]=0, extend tails[3], tails[3]--, tails[4]=1, freq[3]--.
• freq = {1: 0, 2: 0, 3: 0, 4: 1, 5: 1}, tails = {4: 1}.
• 4: freq[4]=1, tails[3]=0, extend tails[4], tails[4]--, tails[5]=1, freq[4]--.
• freq = {1: 0, 2: 0, 3: 0, 4: 0, 5: 1}, tails = {5: 1}.
• 5: freq[5]=1, tails[4]=0, extend tails[5], tails[5]--, freq[5]--.
• freq = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}, tails = {}.
• Step 4: All used, return True.
• Output: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom collections import Counter

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        # Step 1: Count frequencies
        freq = Counter(nums)

        # Step 2: Track sequence ends
        tails = Counter()  # Number of sequences ending at key

        # Step 3: Greedy assignment
        for num in nums:
            if freq[num] == 0:
                continue  # Skip if already used

            freq[num] -= 1  # Use this occurrence

            # Extend existing sequence
            if tails[num - 1] > 0:
                tails[num - 1] -= 1
                tails[num] += 1
            # Start new sequence
            elif freq[num + 1] > 0 and freq[num + 2] > 0:
                freq[num + 1] -= 1
                freq[num + 2] -= 1
                tails[num + 2] += 1
            # Can't form sequence of length ≥ 3
            else:
                return False

        # Step 4: All numbers used, return True
        return True

• Line 1: Import Counter for frequency counting.
• Line 6: Init: Count frequencies in nums.
• Line 9: Init: Counter for sequence ends.
• Lines 12-27: Process:
• Skip used numbers, decrement freq.
• Extend if tail exists, else start new if next two available.
• Return False if neither possible.
• Line 30: Return True if all used.
• Time Complexity: O(n)—single pass through nums.
• Space Complexity: O(n)—hash maps.

This is like a sequence weaver—greedy and fast!

Alternative Solution: Dynamic Programming

Why an Alternative Approach?

The dynamic programming (DP) approach tracks sequence lengths—O(n²) time, O(n) space. It’s more systematic, building states for each prefix, but slower and more complex due to state management. It’s like planning all possible splits step-by-step!

How It Works

Picture this as a sequence planner:

• Step 1: Init DP:
• dp[i][j]: Min unused numbers after splitting prefix i into j sequences.
• Step 2: Fill DP:
• For each i, try splitting into 0 to i+1 sequences.
• Transition: Use consecutive runs, update states.
• Step 3: Check feasibility:
• Return True if any dp[n][j] = 0 (all used).
• Step 4: Return result.

It’s like a state builder—plan and check!

Step-by-Step Example

Example: nums = [1, 2, 3]

• Step 1: Init: dp[0][0] = 0, others inf.
• Step 2: Fill (simplified):
• i=1: dp[1][1] = 0 (start [1]).
• i=2: dp[2][1] = 0 ([1, 2]).
• i=3: dp[3][1] = 0 ([1, 2, 3]).
• Step 3: dp[3][1] = 0, return True.
• Output: True.

Code for DP Approach

Copy codeclass Solution:
    def isPossible(self, nums: List[int]) -> bool:
        # Step 1: Initialize DP
        n = len(nums)
        dp = [float('inf')] * (n + 1)  # Min unused numbers
        dp[0] = 0

        # Step 2: Fill DP (simplified greedy check)
        for i in range(n):
            if dp[i] == float('inf'):
                continue
            j = i
            while j < n and (j == i or nums[j] == nums[j-1] + 1):
                j += 1
                if j - i >= 3:  # Found sequence ≥ 3
                    dp[j] = min(dp[j], dp[i])

        # Step 3: Check if all used
        return dp[n] == 0

• Lines 5-6: Init: dp for unused count.
• Lines 9-16: Fill (simplified):
• From each i, find consecutive run, update if ≥ 3.
• Line 19: Check: All used if dp[n] = 0.
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(n)—dp array.

It’s a sequence checker—plan and verify!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n) time, O(n) space, fast and optimal.
• Cons: Greedy logic less obvious.
• DP (Alternative):
• Pros: O(n²) time, O(n) space, systematic.
• Cons: Slower, complex states.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• Input: [1]
• Output: False.
• Input: [1, 2, 3, 4, 5]
• Output: True ([1, 2, 3], [4, 5] invalid, but [1, 2, 3, 4, 5] works).

Greedy handles these well.

Complexity Breakdown

• Greedy: Time O(n), Space O(n).
• DP: Time O(n²), Space O(n).

Greedy is optimal.

Key Takeaways

• Greedy: Hash map weaving—smart!
• DP: State planning—clear!
• Sequences: Splitting is fun.
• Python Tip: Hash maps rock—see Python Basics.

Final Thoughts: Split That Array

LeetCode 659: Split Array into Consecutive Subsequences in Python is a fun sequence challenge. Greedy with hash maps offers speed and elegance, while DP provides a thorough alternative. Want more? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 128: Longest Consecutive Sequence. Ready to split? Head to Solve LeetCode 659 on LeetCode and weave those sequences today!