C++ O(N) solution, easily understand.


  • 0

    Go through the list, for each integer, we generate a range, this range is represented by a pair<int,int> , the first element is the smallest number on the left side, the second element is the largest number on the right side, then stores this range in a map, which is from an integer to its range. We could use this range to calculate the number of a consecutive sequence.

     int longestConsecutive(vector<int>& nums) {
             // this map is from an integer to its range. 
            unordered_map<int,pair<int, int>> range ;
            // record the longest consecutive sequence
            int maxCount = 0;
            for(auto n : nums)
            {
                if(range.find(n) == range.end())// if the integer we have meet , we don't need to recalculate its range
                {
                    pair<int,int> tmp = {n,n}; // initial its range with itself
                    range[n] = tmp;
                    if(range.find(n-1) != range.end())  // if n - 1 existed, update it's smallest number with the smallest number in the range of n-1
                    {
                        tmp.first = range[n-1].first;
                    }
                    if(range.find(n+1) != range.end())// if n + 1 existed, updates it's largest number with the largest number in the range of n + 1
                    {
                        tmp.second = range[n+1].second;
                    }
                    range[tmp.first].second = tmp.second; //update the largest number in the range of smallest number with current largest number 
                    range[tmp.second].first = tmp.first; //update the smallest number in the range of largest number with current smallest number 
                    maxCount = max(maxCount, tmp.second - tmp.first + 1);
                }
            }
            return maxCount;
            
        }
    

Log in to reply
 

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