An amortized O(n) solution?


  • 0
    Y

    Build and tear down the hash table in two passes of the nums array

    class Solution {
            public:
                    int longestConsecutive(vector<int> &nums) {
                            if (nums.size() == 0) return 0;
                            unordered_map<int, int> ht;
                            int range = 1;
                            for (int i = 0; i < nums.size(); ++i) ht[nums[i]] = 1;
                            /**
                             * In amortized analysis, this for-loop with 2 while-loop
                             * tegother takes O(n) time
                             */
                            for (int i = 0; i < nums.size(); ++i) {
                                    if (ht[nums[i]]) {
                                            int left = nums[i] - 1;
                                            int right = nums[i] + 1;
                                            while (ht[left]) {
                                                    /**
                                                     * Delete left from hash table so that
                                                     * we will not enter "if" statement later
                                                     */
                                                    ht[left] = 0;
                                                    --left;
                                            }
                                            while (ht[right]) {
                                                    ht[right] = 0;
                                                    ++right;
                                            }
                                            range = MAX(range, right - left - 1);
                                    }
                            }
                            return range;
                    }
    };
    

  • 0

    @yan35 Actually you can just use set or multiset to do the same thing where each time just erase the neighbours and then move to the left or right, since set or multiset will always keep the keys inside sorted so it's good enough here.


Log in to reply
 

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