C++ O(n)


  • 1
    B

    got idea from
    https://discuss.leetcode.com/topic/99187/java-o-n-time-o-n-space

    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;
        }
    };

  • 0

    @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!)


  • 1
    B

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


  • 0

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


  • 0
    -

    @coder42 learn a lot?where are u from ?Chinese?


Log in to reply
 

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