# Short C++ O(n) solution with *detailed* explanation and comments

• ``````// O(n) time & space complexity
// greedy
//
// for a number x, there are two options:
// 1. append it to a sequence ending with x-1
// 2. start a new sequence with x
//
// if option 1 is feasible, we should take it since even if we start a new sequence from x,
// we could append it to a sequence ending with x-1
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map<int, int> freq;
for (auto &num : nums) ++freq[num];

// ending[x] means number of sequence ending with x
unordered_map<int, int> ending;

int cnt;
for (auto &num : nums) {
cnt = freq[num];
if (cnt == 0) continue;
if (ending[num-1] >= cnt) {
ending[num] += cnt;
} else {
ending[num] += ending[num-1];
cnt -= ending[num-1];
if (freq[num+1] >= cnt && freq[num+2] >= cnt) {
freq[num+1] -= cnt;
freq[num+2] -= cnt;
ending[num+2] += cnt;
} else {
return false;
}
}
freq[num] = 0;
}
return true;
}
};
``````

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