# 659. Split Array into Consecutive Subsequences

![](/files/-MhckwnKyGIwr8m4M-PX)

![](/files/-Mhckz7JbnCWR6D2hQik)

![](/files/-MiBB6QnXkKWcBs5K_SH)

want to find CIS, 

but make sure it's cis and length >= 3, make sure num, num+1, num+2 exists in the following nums

count: map\[number, freq count => how many keys not checked]

canAppend: map\[append From Which number Ending, how many subsequence has created]

ex: 1 1 2 2 3 3 4

#### 1. 創立新的 subsequnce

起始 by 某數 x, 那要確保 x+1, x+2 都成立

ex: 起始 by 1, 那 2 3 都確保有用, count—

1 x x 2 x x 3

#### 2. append from 某 subseq

1 x x 2 x x 3 xxxx \[4], 假設已經有既有的 subsequence, 後面直接接上

why append, 為什麼不重啟一個新的 subsequence ⇒ 因為 直接 append 可以確保一定成功, 重啟一個新的 , 還要確定後面有 5, 6

```
if (canAppend.getOrDefault(num-1, 0) > 0) {
    canAppend.put(num-1, canAppend.get(num-1)-1);
    canAppend.put(num, canAppend.getOrDefault(num, 0) + 1);
```

如果 current num 前面的數字, 有既有的 subsequence, 那可以拿來繼續拼接,

所以變成

canAppend\[num-1]—;

canAppend\[num]++,

如果都沒有既有的 subsequnce 存在, 那就要做 1. ⇒ 創立新的 subsequnce

```
} else { // start by num
    if (count.getOrDefault(num+1, 0) == 0 || count.getOrDefault(num+2, 0) == 0) {
        return false;
    }
    count.put(num+1, count.get(num+1)-1); // num+1 用過--
    count.put(num+2, count.get(num+2)-1); // num+2 用過--
    canAppend.put(num+2, canAppend.getOrDefault(num+2, 0) + 1);
}
```

```
// 如此, 在 num+2, 有既有的 subsequnce ++
canAppend.put(num+2, canAppend.getOrDefault(num+2, 0) + 1);
```

time: O(n)

space:O(n)

```java
class Solution {
    public boolean isPossible(int[] nums) {
        /*
            0. count[x] == 0 continue; 
            1. start by x, x+1, x+2, used, count--, canAppend[x+2]++
            2. canAppend[x-1] > 0, means we can append by before subsequence, canAppend[x-1]--. canAppend[x]++
        */
        Map<Integer, Integer> count = new HashMap<>(); // map[number, freq count => how many keys not checked]
        Map<Integer, Integer> canAppend = new HashMap<>(); // map[append From Which number Ending, how many subsequence has created]
        
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        for (int num : nums) {
            if (count.get(num) == 0) continue;
            
            count.put(num, count.get(num)-1);
            
            if (canAppend.getOrDefault(num-1, 0) > 0) {
                canAppend.put(num-1, canAppend.get(num-1)-1);
                canAppend.put(num, canAppend.getOrDefault(num, 0) + 1);
                
            } else { // start by num
                if (count.getOrDefault(num+1, 0) == 0 || count.getOrDefault(num+2, 0) == 0) {
                    return false;
                }
                count.put(num+1, count.get(num+1)-1);
                count.put(num+2, count.get(num+2)-1);
                canAppend.put(num+2, canAppend.getOrDefault(num+2, 0) + 1);
            }

        }
        return true;
        
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/greedy/659.-split-array-into-consecutive-subsequences.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.