Longest Consecutive Sequence

Map or Set

Hard

Solution 1:

// Time complexity: O(n)
// Space complexity: O(n)
// Solution 1: offline / online    
// Ref:http://zxi.mytechroad.com/blog/hashtable/leetcode-128-longest-consecutive-sequence/

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
         unordered_map<int, int> h;

         for (int num : nums) {
             if (h.count(num)) continue;

            auto it_l = h.find(num - 1);
            auto it_r = h.find(num + 1);
            //unordered_map<int,int>::iterator it_r = h.find(num + 1);

            int l = it_l != h.end() ? it_l->second : 0;
            int r = it_r != h.end() ? it_r->second : 0;

            if (l > 0 && r > 0) {
                h[num] = h[num - l] = h[num + r] = l + r + 1;
            } else if (l > 0) {
                h[num] = h[num-l] = l + 1;
            } else if (r > 0) {
                h[num] = h[num+r] = r + 1;
            } else {
                h[num] = 1;
            }
         }

         // offline search
        int ans = 0;
        for (const auto& kv : h) {
            ans = max(ans, kv.second);
        }

        return ans;
    }
};

// online solution: update ans every step
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> h;
        int ans = 0;
        for (int num : nums) {
            if (h.count(num)) continue;

            auto it_l = h.find(num - 1);
            auto it_r = h.find(num + 1);

            int l = it_l != h.end() ? it_l->second : 0;
            int r = it_r != h.end() ? it_r->second : 0;
            int t = l + r + 1;

            h[num] = h[num - l] = h[num + r] = t;

            ans = max(ans, t);            
        }

        return ans;
    }
};

Solution 2:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // Hash all the array elements
        // for (int i = 0; i < n; i++)
           // S.insert(arr[i]);
        unordered_set<int> h(nums.begin(), nums.end());

        int ans = 0;
        for (int num : nums) {
            if (!h.count(num-1)) {
                int len = 0;
                while (h.count(num++)) len++;
                ans = max(ans, len);
            }
        }

        return ans;
    }
};

Time Complexity:

At first look, time complexity looks more than O(n). If we take a closer look, we can notice that it is O(n) under the assumption that hash insert and search take O(1) time. The function S.find() inside the while loop is called at most twice for every element. For example, consider the case when all array elements are consecutive. In this case, the outer find is called for every element, but we go inside the if condition only for the smallest element. Once we are inside the if condition, we call find() one more time for every other element.

Ref:

https://www.youtube.com/watch?v=rc2QdQ7U78I