Can we solve this using unordered map?


  • 0
    C

    I have used unordered map as shown below for solving this. C++ reference says that the avg. time complexity for retrieval, insertion and searching in unordered map is constant. So the avg. time complexity of this solution is also linear. Thoughts?

    #include<unordered_map>
        
        class Solution {
        public:
            int longestConsecutive(vector<int> &num) {
                std::unordered_map<int,vector<int>>map;
                int max=0;
                for(int i=0;i<num.size();i++){
                    if(map.count(num[i])>0)continue;
                    vector<int>maxmin_l;
                    vector<int>maxmin_r;
                    if(map.count(num[i]-1)==1)maxmin_l=map[num[i]-1];
                    if(map.count(num[i]+1)==1)maxmin_r=map[num[i]+1];
                    int l,r;
                    if(maxmin_l.size()==2 and maxmin_r.size()==2){
                        l=maxmin_l[1]-maxmin_l[0]+1;
                        r=maxmin_r[1]-maxmin_r[0]+1;
                        vector<int>temp;
                        temp.push_back(maxmin_l[0]);
                        temp.push_back(maxmin_r[1]);
                        map[num[i]]=temp;
                        vector<int>temp2=map[maxmin_l[0]];
                        vector<int>temp3=map[maxmin_r[1]];
                        temp2[1]=maxmin_r[1];
                        temp3[0]=maxmin_l[0];
                        map[maxmin_l[0]]=temp2;
                        map[maxmin_r[1]]=temp3;
                    }else if(maxmin_l.size()==2){
                        vector<int>temp;
                        temp.push_back(maxmin_l[0]);
                        temp.push_back(num[i]);
                        map[num[i]]=temp;
                        l=maxmin_l[1]-maxmin_l[0]+1;
                        r=0;
                        vector<int>temp1=map[maxmin_l[0]];
                        temp1[1]=num[i];
                        map[maxmin_l[0]]=temp1;
                    }else if(maxmin_r.size()==2){
                        vector<int>temp;
                        temp.push_back(num[i]);
                        temp.push_back(maxmin_r[1]);
                        map[num[i]]=temp;
                        r=maxmin_r[1]-maxmin_r[0]+1;
                        l=0;
                        vector<int>temp2=map[maxmin_r[1]];
                        temp2[0]=num[i];
                        map[maxmin_r[1]]=temp2;
                    }else{
                        vector<int>temp;
                        temp.push_back(num[i]);
                        temp.push_back(num[i]);
                        map[num[i]]=temp;
                        l=0;
                        r=0;
                    }
                    if(l+r+1>max)max=l+r+1;
                }
                return max;
            }
        };

  • 0
    R

    I have a simpler solution, that uses unordered_map, but two unordered_map<int, int>. They link the beginning to the end of each sequence and the otherway around.

    At each iteration I create a sequence of one value and I try to merge with a sequence just before and just after, then I inserted the new sequence into the two hash maps.

    class Solution {

    public:

    int longestConsecutive(vector<int> &num) {
        
        if (num.empty()) return 0;
        
        unordered_map<int, int> mapFL; // Hash map that links first -> last
        unordered_map<int, int> mapLF; // Hash map that links last -> first
        
        int maxConsecutive = 1;
        
        for (int val: num) {
            
            // We represent each sequence as [first,last)
            int first = val;
            int last = val + 1;
            
            // Looks if the current element is duplicated:
            if (mapFL.find(first) != end(mapFL)) continue;
            if (mapLF.find(last) != end(mapLF)) continue;
            
            // Is first also last of another sequence?
            auto itLF = mapLF.find(first); 
            if (itLF != end(mapLF)) {
                // YES! Merges the 2 sequences.
                first = itLF->second;
                mapLF.erase(itLF);
            }
    
            // Is last also first of another sequence?
            auto itFL = mapFL.find(last);
            if (itFL != end(mapFL)) {
                // YES! Merges the 2 sequences.
                last = itFL->second;
                mapFL.erase(itFL);
            }
            
            // Saves the merged sequence:
            mapFL[first] = last;
            mapLF[last] = first;
            
            // If the last processed sequence is the biggest, accounts its size:
            maxConsecutive = max(maxConsecutive, last - first);
        }
        
        return maxConsecutive;
    }
    

    };


Log in to reply
 

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