One time traverse solution, simple to understand.


  • -2
    Z
    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            int n=num.size();
            if(n==0 || n==1) return n;
            int res=0;
            int count=0;
            unordered_map<int, int> vIdx; //from value to index in num vector
            vector<int> ls(n,-1);//index for less than one
            vector<int> gt(n,-1);//index for greater than one
            vector<bool> vis(n, false);//already visited flag
            for(int i=0; i<n; i++){
                if(vIdx.count(num[i])==0){
                    vIdx.insert(pair<int,int>(num[i], i));
                }
            }
            for(int i=0; i<n; i++){
                if(vIdx.count(num[i]+1)!=0){
                    gt[i]=vIdx[num[i]+1];
                }
                if(vIdx.count(num[i]-1)!=0){
                    ls[i]=vIdx[num[i]-1];
                }
            }
            for(int i=0; i<n; i++){
                count=0;
                if(!vis[i]){
                    int p=gt[i];
                    while(p!=-1){
                        count++;
                        vis[p]=true;
                        p=gt[p];
                    } 
                    p=i;
                    while(p!=-1){
                        count++;
                        vis[p]=true;
                        p=ls[p];
                    } 
                }
                res=max(res, count);
            }
            return res;
        }
    };

Log in to reply
 

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