LeetCode 659: Split Array into Consecutive Subsequences

Problem Restatement

We are given an integer array nums.

The array is sorted in non-decreasing order.

We need to decide whether we can split all numbers into one or more subsequences such that:

Return True if such a split is possible.

Otherwise, return False.

Input and Output

Example function shape:

def isPossible(nums: list[int]) -> bool:
    ...

Examples

Consider:

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

This can be split into:

1, 2, 3
3, 4, 5

Both subsequences are consecutive and both have length 3.

So the answer is:

True

Another example:

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

This can be split into:

1, 2, 3, 4, 5
3, 4, 5

So the answer is:

True

Now consider:

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

We can form:

1, 2, 3

but then we are left with:

4, 4, 5

That cannot be split into valid consecutive subsequences of length at least 3.

So the answer is:

False

First Thought: Build Subsequences Directly

A direct idea is to scan the numbers and place each number into some subsequence.

For example, when we see 4, we might append it to a subsequence ending at 3.

This sounds reasonable, but we must choose carefully.

If a number can either extend an existing subsequence or start a new one, extending is safer.

Why?

A subsequence that already exists may need the current number to remain valid. Starting a new subsequence creates a new obligation: we must also find the next two numbers.

So the greedy rule is:

Always extend an existing subsequence first if possible.

If we cannot extend one, then we may start a new subsequence of length at least 3.

Key Insight

For a number x, there are only two useful choices.

First, if there is a subsequence ending at x - 1, append x to it.

That subsequence now ends at x.

Second, if no such subsequence exists, start a new subsequence:

x, x + 1, x + 2

This is only possible if x + 1 and x + 2 are still available.

If neither choice is possible, the split cannot be done.

Greedy State

We use two hash maps.

For each number x in nums:

1. If count[x] == 0, skip it because it has already been used.
2. Otherwise, try to append it to a subsequence ending at x - 1.
3. If that is not possible, try to start x, x + 1, x + 2.
4. If that is not possible, return False.

Algorithm

First count the frequency of every number.

Then scan nums from left to right.

For each x:

1. If there are no unused copies of x, continue.
2. Use one copy of x.
3. If end[x - 1] > 0:
   • Decrease end[x - 1].
   • Increase end[x].
4. Else if count[x + 1] > 0 and count[x + 2] > 0:
   • Use one copy of x + 1.
   • Use one copy of x + 2.
   • Increase end[x + 2].
5. Else return False.

If the loop finishes, return True.

Correctness

The algorithm processes numbers in increasing order because nums is sorted.

When the current number is x, any existing subsequence that can use x must end at x - 1. If such a subsequence exists, appending x is always safe. It makes an existing subsequence longer and does not create a new unfinished subsequence.

If no subsequence can be extended, then x must begin a new subsequence. Since every valid subsequence has length at least 3, the new subsequence must include x + 1 and x + 2. If either is unavailable, no valid split can use this copy of x, so returning False is correct.

The algorithm uses every number at most once by decrementing count whenever a number is assigned to a subsequence.

Whenever it starts a new subsequence, it immediately creates one of length 3, so it never leaves a newly started subsequence too short.

Whenever it extends an existing subsequence, the subsequence remains valid or becomes closer to valid if it was just created earlier.

Therefore, if the algorithm finishes, all numbers have been assigned to valid consecutive subsequences of length at least 3. If it returns False, the current number cannot be extended or used to start a valid subsequence, so no valid split exists.

Complexity

Here, n is the length of nums.

Implementation

from collections import Counter, defaultdict
from typing import List

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

        for x in nums:
            if count[x] == 0:
                continue

            count[x] -= 1

            if end[x - 1] > 0:
                end[x - 1] -= 1
                end[x] += 1
            elif count[x + 1] > 0 and count[x + 2] > 0:
                count[x + 1] -= 1
                count[x + 2] -= 1
                end[x + 2] += 1
            else:
                return False

        return True

Code Explanation

We first count unused numbers:

count = Counter(nums)

Then we create a map for subsequence endings:

end = defaultdict(int)

end[v] tells us how many subsequences currently end at value v.

Then we scan each number:

for x in nums:

If this copy has already been used while starting another subsequence, we skip it:

if count[x] == 0:
    continue

Otherwise, we consume one copy of x:

count[x] -= 1

Now we first try to extend a subsequence ending at x - 1:

if end[x - 1] > 0:
    end[x - 1] -= 1
    end[x] += 1

If no subsequence can be extended, we try to start a new subsequence of length 3:

elif count[x + 1] > 0 and count[x + 2] > 0:
    count[x + 1] -= 1
    count[x + 2] -= 1
    end[x + 2] += 1

This creates:

x, x + 1, x + 2

and records that the new subsequence ends at x + 2.

If neither option is possible, x cannot belong to any valid subsequence:

else:
    return False

If all numbers are processed successfully, the split is valid:

return True

Testing

def run_tests():
    s = Solution()

    assert s.isPossible([1, 2, 3, 3, 4, 5]) is True
    assert s.isPossible([1, 2, 3, 3, 4, 4, 5, 5]) is True
    assert s.isPossible([1, 2, 3, 4, 4, 5]) is False

    assert s.isPossible([1, 2, 3]) is True
    assert s.isPossible([1, 2]) is False

    assert s.isPossible([1, 2, 3, 4, 5, 6]) is True
    assert s.isPossible([1, 2, 3, 4, 5, 5, 6, 7]) is True

    assert s.isPossible([1, 2, 3, 4, 4, 5, 6]) is False

    print("all tests passed")

run_tests()

Test meaning: