C++ O(n)

• use two hashMap, one count for the freq of all num, one count for the freq of end num of subsequence.

When construct subsequence, if we need to start a new num, we find consecutive 3 num all at once. if we cannot find all 3 num, then return false.

``````class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int,int>pool, ends;
for(auto e : nums) pool[e]++;
for(auto e : nums)
{
if(pool[e] == 0) continue;
if(ends[e-1] > 0)
{
ends[e-1]--;
ends[e]++;
}
else if(pool[e+1] > 0 && pool[e+2] > 0)
{
pool[e+1]--;
pool[e+2]--;
ends[e+2]++;
}
else
return false;
pool[e]--;
}
return true;
}
};``````

• @beetlecamera said in C++ O(n):

``````        if(ends[e-1] > 0)
{
ends[e-1]--;
ends[e]++;
}
``````

Hey @beetlecamera This is very nice.
I could understand that if we need to start a new consecutive sequence from, say , "e" in your code, we need find consecutive 3 num after current "e" all at once. Thus if there is anyway to start a new consecutive sequence, the new start should be at least "e+2".

However, I still don't get the way you implement "ends" to record "the freq of end num of subsequence". Why if ends[e-1]>0 then we need to ends[e-1]--; and ends[e]++; ? what does "ends[e-1]--" stands for ?

It would be great to give us some clues of mathematical correctness behind this algorithm. (But this solution is smart and clear! Thanks!)

• @coder42 said in C++ O(n):

@beetlecamera said in C++ O(n):

``````        if(ends[e-1] > 0)
{
ends[e-1]--;
ends[e]++;
}
``````

Hey @beetlecamera This is very nice.
I could understand that if we need to start a new consecutive sequence from, say , "e" in your code, we need find consecutive 3 num after current "e" all at once. Thus if there is anyway to start a new consecutive sequence, the new start should be at least "e+2".

However, I still don't get the way you implement "ends" to record "the freq of end num of subsequence". Why if ends[e-1]>0 then we need to ends[e-1]--; and ends[e]++; ? what does "ends[e-1]--" stands for ?

It would be great to give us some clues of mathematical correctness behind this algorithm. (But this solution is smart and clear! Thanks!)

ends is a HashMap that count the number of subsequence that end at the number. For example, if we have ends[5] = 2, which means we have 2 subsequence ends with 5, such as 12345 and 345 both ends with 5.

Now back to your question, with a greedy algorithm, when we process a number from input array, say 5, we first check if there is any subsequence ends with number 4, that's why we have if(ends[e-1] > 0) . The trick is if we have a subsequence ends with 4, we would append 5 to the end of the subsequence, then the subsequence would ends with 5 now, and it no longer ends with 4. That is why we have ends[e-1]--; and ends[e]++;. If we have another 5 to process, now we no longer have a subsequence ends at 4, then we need to construct a new subsequence.

• @beetlecamera Thanks! Your explanation is very detailed and straightforward! Lear a lot from you! :)

• @coder42 learn a lot？where are u from ？Chinese？

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