Reference: LeetCode
Difficulty: Medium

## 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:

## Analysis

### Map + PriorityQueue

Reference:

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.
• 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]:

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>.

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]:

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:

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.