13-line C++ solution


  • 19
    G

    Thought I would share it here. May be useful for some one. The algorithm itself is pretty straightforward. But it benefited quite much from the neat expression of C++ idioms. Comments are appreciated!

    int longestConsecutive(const vector<int> &num) {
        unordered_set<int> s(num.begin(), num.end()), searched;
        int longest = 0;
        for (int i: num) {
            if (searched.find(i) != searched.end()) continue;
            searched.insert(i);
            int j = i - 1, k = i + 1;
            while (s.find(j) != s.end()) searched.insert(j--);
            while (s.find(k) != s.end()) searched.insert(k++);
            longest = max(longest, k - 1 - j);
        }
        return longest;
    }

  • -5
    O

    The time complexity is O(n^2) in the worse case here.


  • 1
    G

    Thanks for your comment oujiafan. But personally I don't think so. Because we have an unordered_set searched, this guards every element will only be visited once. Therefore I suppose it's O(n)? And note this is an unordered_set, which has O(1) insertion and find operations.


  • 0
    C

    Agree. It's O(n).


  • -4
    H

    +1 Nice solution!

    You can reduce the space complexity by using a unordered_map<int, bool> instead of two unordered_set. bool value would keep a track if the value has been visited or not.

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            unordered_map<int, bool> visited;
            int res=0;
            
            for(int i=0; i<int(num.size()); i++)
                visited[num[i]]=false;
                
            for(int i=0; i<int(num.size()); i++)
            {
                int curr=1;
                
                if(visited[num[i]]==true)
                    continue;
                
                visited[num[i]]=true;
                
                int less=num[i]-1, more=num[i]+1;
                
                while(visited.find(less)!=visited.end())
                {
                    visited[less]=true;
                    less--;
                    curr++;
                }
                
                while(visited.find(more)!=visited.end())
                {
                    visited[more]=true;
                    more++;
                    curr++;
                }
                
                res=max(res, curr);
            }
            
            return res;
        }
    };

  • 0
    C

    I agree with you, it's a O(n^2) solution, for example, 1, 2, 3, 4 when insert 4, (3, 2, 1) will be repeated inserted.


  • 0
    X

    Hello from 0611 classmate :)


  • 0
    G

    hahah! wave~~~~~


  • 0
    B

    unordered_set's find() is not supposed to be O(1)
    http://www.cplusplus.com/reference/unordered_set/unordered_set/find/


  • 0
    G

    Oh no! You're right... O(1) is just the average time but O(n) is in the worst case. Thank you so much for pointing it out. New lesson learned!


  • 0
    A

    hello from Anjoy....0610 uster


  • 0
    A

    That's the case for all hash tables. O(n) worst case but /amortized/ O(1).


  • 0
    M

    I still do not understand why this is O(n), even if searched.find(i) takes only O(1).

    Changes made on 'searched' in the while loop don't reduce the iteration of the for loop, so the for loop runs n times, and the while loop sometimes runs more than one time(obviously). Therefore, the average time complexity will be more than O(n).

    Please correct me.


  • 0
    Z

    I use the set directly, not the unorderd_set, it accepted in 32ms. And your code is 38ms, why? maybe when the test data becomes large? the performance of unorderd_set would be displayed?

    class Solution {
    public:
       // my solution
        int longestConsecutive(vector<int> &num) {
            int n = num.size();
            for(int i = 0; i < n; i++)
                hset.insert(num[i]);
            int maxResult =1, result = 1;
            set<int>::iterator iter = hset.begin();
            set<int>::iterator iter2 = hset.begin();;
            iter2++;
            while(iter2 != hset.end()){
                if(*iter2 == (*iter)+1) result++;
                else result = 1;
                maxResult = max(result, maxResult);
                iter2 ++;
                iter ++;
            }
            return maxResult;
        }
    private:
        set<int> hset;
    };

  • 0
    S

    I think is O(nlogn) consider the following test case :
    1 3 2 5 7 6 9 11 10 13 15 14 12 8


Log in to reply
 

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