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

# 659    Split Array into Consecutive Subsequences

## 659. [Split Array into Consecutive Subsequences](https://leetcode.com/problems/split-array-into-consecutive-subsequences/description/)

## 1. Question

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]

## 2. Implementation

**(1) Heap**

思路：建立一个map，每个序列当前结尾的number作为key, value是该number对应的minHeap,存储以该number结尾的序列的长度. 当一个number出现在两个或以上的序列的末端，我们尽量把number + 1加在最短的序列后面(所以用minHeap). 最后遍历整个map，当出现以key结尾的序列的长度小于3时，返回false

```java
class Solution {
    public boolean isPossible(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        PriorityQueue<Integer> minHeap = null;
        for (int num : nums) {
            minHeap = map.getOrDefault(num - 1, new PriorityQueue<>());
            int len = minHeap.size() == 0 ? 0 : minHeap.remove();
            minHeap = map.getOrDefault(num, new PriorityQueue<>());
            minHeap.add(len + 1);
            map.put(num, minHeap);
        }

        for (int key : map.keySet()) {
            for (int len : map.get(key)) {
                if (len < 3) {
                    return false;
                }
            }
        }
        return true;
    }
}
```

**(2) Two HashMap**

(1) 用一个map记录每个number出现的次数，用另一个map记录当前的number是否可以加到一个现有的subsequence里

(2) 对于每个数，它要不成为一个有连续3个数的subsequence的开头，要不可以加在一个现有的subsequence里，如果这两个条件都不满足，说明该数组不能split成题目要求的subsequence

```javascript
class Solution {
    public boolean isPossible(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();

        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        for (int num : nums) {
            if (freq.get(num) == 0) continue;

            // Current num can be appended to a subsequence
            if (need.getOrDefault(num, 0) > 0) {
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            }
            // Current num be the start of a new subsequence
            else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            }
            // We can not split the array into subsequences with at least 3 consecutive numbers due to current number
            else {
                return false;
            }
            freq.put(num, freq.get(num) - 1);
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

**HashMap** + **Heap:** 时间复杂度O(nlogk + nk),k为以num为结尾的subsequence的个数 空间复杂度O(nk)

**Two HashMap:** 时间复杂度O(n), 空间复杂度O(n)