Reference: LeetCode

Difficulty: Medium

My Post: All-In-One Java Solution (Map + PQ & Two Maps) with Explanation, Examples, and Comments

## Problem

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.

**Note:** The length of the input is in range of `[1, 10000]`

.

**Example:**

1 | Input: [1,2,3,3,4,5] |

1 | Input: [1,2,3,3,4,4,5,5] |

## Analysis

### Map + PriorityQueue

Reference:

- LeetCode 659. Split Array into Consecutive Subsequences 解题报告（Python）
- LeetCode[659]Split Array into Consecutive Subsequences(Java)
- Java O(n) time & O(1) space solution – greedily extending shorter subsequence

We use a `HashMap<Integer, PriorityQueue<Integer>>`

to store the information we need to process the list. For current number `val`

, we compare its value to its predecessor to see if their difference is $1$.

By `map.get(val)`

, we have a priority queue, which stores all available lengths of sequence ending with value `val`

. The reason why we use a priority queue is that when we encounter a new value `val`

, we want to append it to the shortest sequence that needs most “help”. We want all sequences we have to satisfy the requirement `>= k`

. For example, `[1, 2, 3]`

and `[2, 3]`

: The next value is `4`

, we will add it to `[2, 3]`

and it becomes `[2, 3, 4]`

rather than adding it to `[1, 2, 3]`

. This is the idea of greedy algorithm, since we always go for the shortest length of sequence at each step.

Algorithm:

- For each current value
`val`

:- If
`val - 1`

exists in the map, we get the priority queue by`map.get(val - 1)`

and poll the shortest sequence’s length and offer it into the priority queue in`map.get(val)`

. - If
`val - 1`

does not exists in the map, or its priority queue is empty, we start over from this element and offer`1`

into the`val`

‘s priority queue.

- If
- Finally, we iterate the map’s values, and poll each sequence’s length by
`pq.poll()`

and check if all of then satisfy the requirement.

For example, we have a sequence `[1, 2, 3, 3, 4, 4, 5, 5]`

:

1 | val map case |

Code with comments:

1 | public boolean isPossible(int[] nums) { |

**Time:** $O(N\log{N})$**Space:** $O(N)$

### Two Maps

Reference: Java O(n) Time O(n) Space

Thanks `marcohwlam`

for the example that many post writers don’t even add to their posts. Not mention the code without comments. Drives me crazy!

**Note:** I still don’t know why it works though, but at least I now know how it works.

This time, we have two hash maps: `freqMap`

and `subMap`

.

`freqMap`

: Count the frequency of all numbers.`subMap`

: Store qualified (`>= 3`

) subsequences. It is not obvious though.- For example,
`<4, 1>`

means we have already`one`

qualified subsequence (e.g.`[1, 2, 3]`

) and it will continue from`4`

. Then later when we encounter a value`4`

, we can append`4`

to the current subsequence and update the map to`<4, 0>, <5, 1>`

.

- For example,

Algorithm:

- Iterate through the array to get the frequency of all the elements.
- Iterate through the array once more to see:
`Case 1`

: If`val`

‘s frequency is used up? Yes =>`continue;`

to the next`val`

.`Case 2`

: If each element can be appended to a previously constructed consecutive subsequence.`Case 3`

: If it can be the start of a new consecutive sequence.`Case 4`

: Returns`false`

.- Remember to decrement the frequency of
`val`

in`freqMap`

at each time.

For example, we have a sequence `[1, 2, 3, 3, 4, 4, 5, 5]`

:

1 | Init: freqMap = <1, 1>, <2, 1>, <3, 2>, <4, 2>, <5, 2> |

Code with comments:

1 | public boolean isPossible(int[] nums) { |

**Time:** $O(N)$**Space:** $O(N)$

### Extra

$O(1)$ space:

Java O(n) time & O(1) space solution – greedily extending shorter subsequence

The original code:

1 | public boolean isPossible(int[] nums) { |