> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/greedy/659.-split-array-into-consecutive-subsequences.md).

# 659. Split Array into Consecutive Subsequences

Given an array `nums` sorted in ascending order, return `true` if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

**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
```

**Constraints:**

* `1 <= nums.length <= 10000`

```cpp
// Greedy
bool isPossible(vector<int>& nums) { // time: O(n); space: O(n)
    unordered_map<int, int> cnt, tail;
    for (const int& num : nums) ++cnt[num];
    for (const int& num : nums) {
        if (cnt[num] == 0) continue;
        --cnt[num];
        if (tail[num - 1] > 0) {
            --tail[num - 1];
            ++tail[num];
        } else if (cnt[num + 1] > 0 && cnt[num + 2] > 0) {
            --cnt[num + 1];
            --cnt[num + 2];
            ++tail[num + 2];
        } else return false;
    }
    return true;
}
```

```cpp
// Greedy
bool isPossible(vector<int>& nums) { // time: O(n); space: O(n)
    unordered_map<int, int> cnt, need;
    for (int num : nums) ++cnt[num];
    for (int num : nums) {
        if (!cnt[num]) continue;
        --cnt[num];
        if (need[num] > 0) {
            --need[num];
            ++need[num + 1];
        } else if (cnt[num + 1] > 0 && cnt[num + 2] > 0) {
            --cnt[num + 1];
            --cnt[num + 2];
            ++need[num + 3];
        } else return false;
    }
    return true;
}
```