Simple C++ O(N) solution using set.


  • 5
    H
    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            int len = 0, candidate, val;
            unordered_set<int> set(nums.begin(), nums.end());
            while (!set.empty()) {
                val = *set.begin();
                set.erase(val);
                candidate = 1;
                for (int i = val + 1; set.find(i) != set.end(); ++i) {
                    set.erase(i);
                    candidate++;
                }
                for (int i = val - 1; set.find(i) != set.end(); --i) {
                    set.erase(i);
                    candidate++;
                }
                len = max(len, candidate);
            }
            return len;
        }
    };

  • 0
    C

    the insertion operation of set for each element is lg(N)


  • 0
    V

    Yes, but (s)he is using an unordered_set.


  • 0
    C

    what is the complexity of set.find(i) ? Is it less than O(n) or O(logn)


  • 0
    K

    Complexity of unordered_set.find is amortized O(1)


Log in to reply
 

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