I think the problem is not well formulated.


  • 0
    R

    I have a simple solutiion that passes the test:

    class Solution {
    
    public:
        int longestConsecutive(vector<int> &num) {
            
            if (num.empty()) return 0;
    
            set<int> set(begin(num), end(num));
            
            auto it = set.begin();
            int prev = *it;
            int numConsecutive = 1;
            int maxConsecutive = 1;
            for (++it; it != set.end(); ++it) {
                
                int current = *it;
                if (current == prev + 1) {
                    
                    numConsecutive++;
                }
                else {
                    
                    maxConsecutive = max(maxConsecutive, numConsecutive);
                    numConsecutive = 1;
                }
                
                prev = current;
            }
            
            return max(maxConsecutive, numConsecutive);
        }
    };
    

    The solution uses a set. It is not O(n) because every insertion if O(log(N)). The solution is
    O(N log(N)).

    A solution involving an hash map has the same problem, is O(N^2) in case num contains only identical elements.

    Bucket sort, that is O(N), doesn't work because requires a small set of elements (and there is a specific test case passing INT_MAX and INT_MIN beside the values of the array.

    So I'm seriously interested now to know what is the O(n) solution.


  • 0
    B
    This post is deleted!

  • 2
    R

    I was wrong about hash maps.

    Here you can see my second solution using two of them. O(n). ;-)

    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;
        }
    };

  • 2
    S

    Hello, an unordered_set is used as the hash table in my case. It is O(N) because each element is only scanned once. For the 1st element (beginning of the set), I search its neighbors in two directions until it fails to find any. Erase all neighbors found from the set, also this element at the end. In this way, a single sequence is scanned and erased. Go to next element (still the beginning of the set), and repeat the process.

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            if (num.size() == 0)
                return 0;
            
            // for each element in the set, search to left and right
            // remove this element and all its found neighbors from the set
            // stop when search failed on each direction
            // each element is only scanned exactly one time
            // so the overall complexity is O(N)
            int maxL = 1;
            int curL = 1;
            unordered_set<int> keys(num.begin(), num.end());
            while(!keys.empty()) { 
                auto cur = keys.begin();
                int i1 = *cur;
                while (!keys.empty()) { // search to right
                    auto it = keys.find(++i1);
                    if (it != keys.end()) {
                        curL++;
                        keys.erase(it);
                    }
                    else {
                        break;
                    }
                }
                
                i1 = *cur;
                while (!keys.empty()) { // search to left
                    auto it = keys.find(--i1);
                    if (it != keys.end()) {
                        curL++;
                        keys.erase(it);
                    }
                    else {
                        break;
                    }
                }
                keys.erase(cur);
                
                if (curL > maxL)
                    maxL = curL;
                curL = 1;
            } 
            return maxL;
        }
    };

  • 0
    R

    Yes my second commentary is confirmin your solution. Just my second solution may be faster because does everything on place with only one passage but can be improved a lot catching consecutive numbers if the sequence is not completely unsorted.


Log in to reply
 

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