## 659. Split Array into Consecutive Subsequences

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

```Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5
```

Example 2:

```Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5
```

Example 3:

```Input: [1,2,3,4,4,5]
Output: False
```

Note:

1. The length of the input is in range of [1, 10000]

b'
\n\n
\n

#### Approach #1: Opening and Closing Events [Accepted]

\n

Intuition

\n

We can think of the problem as drawing intervals on a number line. This gives us the idea of opening and closing events.

\n

To illustrate this concept, say we have `nums = [10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13]`, with no `9`s and no `14`s. We must have two sequences start at 10, two sequences start at 11, and 3 sequences end at 12.

\n

In general, when considering a chain of consecutive integers `x`, we must have `C = count[x+1] - count[x]` sequences start at `x+1` when `C > 0`, and `-C` sequences end at `x` if `C < 0`. Even if there are more endpoints on the intervals we draw, there must be at least this many endpoints.

\n

Also, if for example we know some sequences must start at time `1` and `4` and some sequences end at `5` and `7`, to maximize the smallest length sequence, we should pair the events together in the order they occur: ie., `1` with `5` and `4` with `7`.

\n

Algorithm

\n

For each group of numbers, say the number is `x` and there are `count` of them. Furthermore, say `prev, prev_count` is the previous integer encountered and it\'s count.

\n

Then, in general there are `abs(count - prev_count)` events that will happen: if `count > prev_count` then we will add this many `t`\'s to `starts`; and if `count < prev_count` then we will attempt to pair `starts.popleft()` with `t-1`.

\n

More specifically, when we have finished a consecutive group, we will have `prev_count` endings; and when we are in a consecutive group, we may have `count - prev_count` starts or `prev_count - count` endings.

\n

For example, when `nums = [1,2,3,3,4,5]`, then the starts are at `[1, 3]` and the endings are at `[3, 5]`. As our algorithm progresses:

\n
\n
• When `t = 1, count = 1`: `starts = `
• \n
• When `t = 2, count = 1`: `starts = `
• \n
• When `t = 3, count = 2`: `starts = [1, 3]`
• \n
• When `t = 4, count = 1`: `starts = `, since `prev_count - count = 1` we process one closing event, which is accepted as `t-1 >= starts.popleft() + 2`.
• \n
• When `t = 5, count = 1`: `starts = `
• \n
\n

And at the end, we process `prev_count` more closing events `nums[-1]`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `nums`. We iterate over the array and every event is added or popped to `starts` at most once.

\n
• \n
• \n

Space Complexity: , the size of `starts`.

\n
• \n
\n
\n

#### Approach #2: Greedy [Accepted]

\n

Intuition

\n

Call a chain a sequence of 3 or more consecutive numbers.

\n

Considering numbers `x` from left to right, if `x` can be added to a current chain, it\'s at least as good to add `x` to that chain first, rather than to start a new chain.

\n

Why? If we started with numbers `x` and greater from the beginning, the shorter chains starting from `x` could be concatenated with the chains ending before `x`, possibly helping us if there was a "chain" from `x` that was only length 1 or 2.

\n

Algorithm

\n

Say we have a count of each number, and let `tails[x]` be the number of chains ending right before `x`.

\n

Now let\'s process each number. If there\'s a chain ending before `x`, then add it to that chain. Otherwise, if we can start a new chain, do so.

\n

It\'s worth noting that our solution can be amended to take only additional space, since we could do our counts similar to Approach #1, and we only need to know the last 3 counts at a time.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `nums`. We iterate over the array.

\n
• \n
• \n

Space Complexity: , the size of `count` and `tails`.

\n
• \n
\n
\n

Analysis written by: @awice. Approach #2 inspired by @compton_scatter.

\n
'