# Simple C++ Greedy O(nlogn) Solution (with explanation)

• The Algorithm

Maintain a set of consecutive sequences, call this set `s`. `s` begins as an empty set of consecutive sequences.

Now, iterate through each `num` in `nums`. For each iteration, if there exists a consecutive sequence in `s` that ends with element `num-1`, then append `num` to the end of the shortest such sequence; otherwise, create a new sequence that begins with `num`.

The problem has a solution (i.e. the array can be split into consecutive subsequences such that each subsequence consists of at least 3 consecutive integers) if and only if each sequence in `s` has size greater than or equal to 3.

Proof of Algorithm

Why does this algorithm work? It was intuitive to me, but I could not indisputably prove that it was correct. Hopefully, someone else can prove it.

Implementation

We don't need to actually store each sequence. Instead, we just need to know (1) the number of sequences that end at a particular element, and (2) the size of each of those sequences. To implement this, we can have an unordered map `backs` to represent the sequences: `backs[key]` returns a priority queue (smallest value at top) of the sizes of all sequences that end with element `key`. Now that we have (1) and (2), we can implement the algorithm above without knowing each particular sequence.

For each `num` in `nums`, if there exists any sequence that ends with `num-1` (i.e. if `backs[num-1]` is a non-empty priority queue), then find such a sequence with the smallest possible size (get the smallest value from the priority queue at `backs[num-1]`). Now, the sequence will be extended by 1 since we will add `num` to it. So pop the smallest value `count` from the priority queue at `backs[num-1]`, and add a new value `count+1` to the priority queue at `backs[num]`.

If no sequence was found that ends in `num-1` (i.e. `backs[num-1]` is empty), then create a new sequence. In other words, add `1` to the priority queue at `backs[num]`.

The Code

``````class Solution {
public:
bool isPossible(vector<int>& nums)
{
unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> backs;

// Keep track of the number of sequences with size < 3
int need_more = 0;

for (int num : nums)
{
if (! backs[num - 1].empty())
{	// There exists a sequence that ends in num-1
// Append 'num' to this sequence
// Remove the existing sequence
// Add a new sequence ending in 'num' with size incremented by 1
int count = backs[num - 1].top();
backs[num - 1].pop();
backs[num].push(++count);

if (count == 3)
need_more--;
}
else
{	// There is no sequence that ends in num-1
// Create a new sequence with size 1 that ends with 'num'
backs[num].push(1);
need_more++;
}
}
return need_more == 0;
}
};
``````

Improvements

I know that there are O(n) solutions out there that use different algorithms. Can my algorithm be implemented more efficiently to be O(n) instead of O(nlogn)?

Thoughts?

• Nice solution, appreciate it

• Hi, I think we almost have the same idea. The reason we have O(nlogn) instead of O(n) is because of the priority queue. In fact, append to the shortest subsequence is not necessary. Any subsequences with the length larger than 3 are equal.
A way to solve that is to use another hashmap or vector as a counter to count how many times each number show up in the original sequence. Then, do another for loop to formulate subsequences. This time, when trying to form a new subseuqences, make sure you get 3 number ahead of time.

• Actually, you don't need the priority_queue, just an array contains the number of sequences of length 1, 2, 3+ is enough. Then the time is O(n).

My python code:

``````def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
chains = {}
for x in nums:
#count of chains end with x and having length 0,1,2,3+
pre = chains.setdefault(x-1, [0,0,0,0])
cur = chains.setdefault(x, [0,0,0,0])
#add x to the shortest chain
if pre[1] > 0:
pre[1] -= 1
cur[2] += 1
elif pre[2] > 0:
pre[2] -= 1
cur[3] += 1
elif pre[3] > 0:
pre[3] -= 1
cur[3] += 1
else:
cur[1] += 1

for x in chains:
if chains[x][1] or chains[x][2]:
return False
return True
``````

• @jay520 noob question here, how is your complexity nlogn ?

• I think this is also O(n), why not?
Quote:
class Solution {
public:
bool isPossible(vector<int>& nums)
{
unordered_map<int, priority_queue<int, vector<int>, std::greater<int>>> backs;

``````	// Keep track of the number of sequences with size < 3
int need_more = 0;

for (int num : nums)
{
if (! backs[num - 1].empty())
{	// There exists a sequence that ends in num-1
// Append 'num' to this sequence
// Remove the existing sequence
// Add a new sequence ending in 'num' with size incremented by 1
int count = backs[num - 1].top();
backs[num - 1].pop();
backs[num].push(++count);

if (count == 3)
need_more--;
}
else
{	// There is no sequence that ends in num-1
// Create a new sequence with size 1 that ends with 'num'
backs[num].push(1);
need_more++;
}
}
return need_more == 0;
}
``````

};

• @csytracy Hey, could you please give your code for the same ??

• Hi, my idea is also go through the array but achieving O(n), you can check it out here:
https://discuss.leetcode.com/topic/100988/c-o-n-solution-two-pass

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.