# 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:

| Rule | Meaning |
|---|---|
| Consecutive | Each number is exactly `1` larger than the previous number |
| Minimum length | Every subsequence has length at least `3` |
| Use all numbers | Every element in `nums` must be used exactly once |

Return `True` if such a split is possible.

Otherwise, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Output | `True` if the array can be split, otherwise `False` |
| Subsequence rule | Values must be consecutive increasing integers |
| Length rule | Each subsequence must have length at least `3` |
| Usage rule | Every input element must be used exactly once |

Example function shape:

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

## Examples

Consider:

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

This can be split into:

```text
1, 2, 3
3, 4, 5
```

Both subsequences are consecutive and both have length `3`.

So the answer is:

```python
True
```

Another example:

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

This can be split into:

```text
1, 2, 3, 4, 5
3, 4, 5
```

So the answer is:

```python
True
```

Now consider:

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

We can form:

```text
1, 2, 3
```

but then we are left with:

```text
4, 4, 5
```

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

So the answer is:

```python
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:

```text
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:

```text
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.

| Map | Meaning |
|---|---|
| `count` | How many copies of each number are still unused |
| `end` | How many subsequences currently end at a given number |

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once after counting |
| Space | `O(n)` | The hash maps may store many distinct values |

Here, `n` is the length of `nums`.

## Implementation

```python
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:

```python
count = Counter(nums)
```

Then we create a map for subsequence endings:

```python
end = defaultdict(int)
```

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

Then we scan each number:

```python
for x in nums:
```

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

```python
if count[x] == 0:
    continue
```

Otherwise, we consume one copy of `x`:

```python
count[x] -= 1
```

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

```python
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`:

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

This creates:

```text
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:

```python
else:
    return False
```

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

```python
return True
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[1,2,3,3,4,5]` | Standard valid split into two length-3 subsequences |
| `[1,2,3,3,4,4,5,5]` | Valid split where one subsequence becomes longer |
| `[1,2,3,4,4,5]` | Standard impossible case |
| `[1,2,3]` | Smallest valid subsequence |
| `[1,2]` | Too short to be valid |
| `[1,2,3,4,5,6]` | One long consecutive subsequence |
| `[1,2,3,4,5,5,6,7]` | Requires extending and starting subsequences |
| `[1,2,3,4,4,5,6]` | Extra duplicate cannot form a valid length-3 chain |