One easy solution with 20ms


  • 0
    H

    The target is to put all the number into a hash. Then loop around the vector of nums. Then to find its lowest and highest adjacent neighbours. If found, then delete those neighbours from the hash.

    The algorithm is linear, because each number will be accessed exactly twice, one is to find the neighbour, second is on the loop entry.

    Here is the code:

    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> nSet(nums.begin(), nums.end());
        
        int maxLen = 1;
        for (auto n:nums) {
            int lower = n-1;
            while (nSet.count(lower)) {
                nSet.erase(lower--);
            }
            int higher = n+1;
            while (nSet.count(higher)) {
                nSet.erase(higher++);
            }
            maxLen = max(higher-lower-1, maxLen);
        }
        return maxLen;
    }

Log in to reply
 

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