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


  • 1
    S
    // 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;
        }
    };
    

Log in to reply
 

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