Overkill solution but one pass


  • 0
    Q

    This was what came up to my mind when I first saw this question.
    It is slow (40ms) but it is one pass, so it can be used to process streaming input

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
    //my own way
            int n = nums.size(); if(!n) return 0;
            int Max = 1;
            unordered_map<int, pair<int,int>> table;
            unordered_set<int> set;
            
            for(int i : nums) {
                if(set.count(i)) continue;
                set.insert(i);
                auto prevIt = table.find(i-1);
                auto nextIt = table.find(i+1);
                if(prevIt == table.end() && nextIt == table.end()) {
                    table.insert(make_pair(i, make_pair(i,i)));
                } else
                if(prevIt != table.end() && nextIt == table.end())
                {
                    auto itv = prevIt->second;
                    table.erase(prevIt);
                    table.erase(itv.first);
    
                    table.insert(make_pair(i,make_pair(itv.first, i)));
                    table.insert(make_pair(itv.first,make_pair(itv.first, i)));
                    Max = max(Max, i-itv.first + 1);
                } else 
                if(prevIt == table.end() && nextIt != table.end())
                {
                    auto itv = nextIt->second;
                    table.erase(nextIt);  //forward interval
                    table.erase(itv.second);
                    table.insert(make_pair(i, make_pair(i, itv.second)));
                    table.insert(make_pair(itv.second, make_pair(i, itv.second)));
                    Max = max(itv.second -i+1, Max);
                } else { //need to merge
                    auto prevItv =  prevIt->second; auto nextItv = nextIt->second;
                    auto newItv = make_pair(prevItv.first, nextItv.second);
                    table.erase(prevIt); table.erase(nextIt);
                    table.erase(prevItv.first); table.erase(nextItv.second);
                    table.insert(make_pair(prevItv.first, newItv));
                    table.insert(make_pair(nextItv.second, newItv));
                    Max = max(Max, nextItv.second - prevItv.first +1);
                    
                }
    
        }
        
        return Max;
    }
    

    };


Log in to reply
 

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