O(n) time and O(n) space C++ solution in less than 20 lines


  • 0
    A

    The idea here is to create a map of element [ i ] ==> length of consecutive sequence upto element i .
    The answer would simply be the maximum value of second element of the map.
    Again we all are assuming map lookups are in O(1) .

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            map<int,int> mp;
            for(int i=0;i<num.size();++i)
                mp[num[i]] = 1;
            for(map<int,int>::iterator i=mp.begin();i!=mp.end();++i){
               if(mp.find(i->first-1) != mp.end()){
                   i->second = mp[i->first-1]+1;
               } 
            }
            int ans=0;
            for(map<int,int>::iterator i=mp.begin();i!=mp.end();++i){
                ans = max(ans,i->second);
            }    
            return ans;
        }
    };

  • 12
    W

    Nice! But there might be a small problem that's easy to fix.

    It seems to me that this would only work if map stores entries in ascending order, which would make it O(nlogn) instead of O(n).


  • 0
    V

    What's the run time?
    My solution is 52ms


  • 0
    A

    I think your solution costs O(nlogn) in time.


  • 3
    M

    The map's insert operation is O(lgn), so your solution is O(nlgn)


  • 0
    J

    I agree with you, this method only works if map stores entries(first value) in ascending order;But you must attention that the key value of the map is sorted from small to large by using red-black tree. So this solving method is right.


  • 0
    E

    Just switch from map to unordered_map


  • 0
    Y

    The solution depends on the map to have the numbers ordered when you iterate through it. So you can't use unordered_map.


  • 0
    T

    map<T, T> in c++ is a tree structure which has a O(logn) complexity. The hash map in C++11 is unordered_map


  • 0

Log in to reply
 

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