128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.

Your algorithm should run in O(n) complexity.

S1: hash map O(N)

用hash map在连续序列起始和结尾处存储其长度，并逐步更新起始和结尾处的长度

boundary[i]表示以i为开头或结尾的consecutive sequence的长度，重复元素不予计算

    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> boundary;
        int maxLen = 0;
        for (int i : nums) {
            if (boundary.find(i) == boundary.end()) {
                int left = 0, right = 0;
                if (boundary.find(i - 1) != boundary.end()) {
                    left = boundary[i - 1];
                } 
                if (boundary.find(i + 1) != boundary.end()) {
                    right = boundary[i + 1];
                } 
                int len = left + right + 1;
                boundary[i] = len;  //存储boundary[i]只是为了避免重复计算，这个值没有意义，也不会影响计算
                boundary[i - left] = len;
                boundary[i + right] = len;
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }

S2: Union Find O(N)

hashmap root存储每个元素的‘老大哥’，len存储每个老大哥所在集合个数，len在connect的时候更新。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() > 0) {
            maxLen = 1;
        } 
        for (int i : nums) {
            if (len.find(i) == len.end()) {
                root[i] = i;
                len[i] = 1;
                if (root.find(i - 1) != root.end()) {
                    connect(i - 1, i);
                }
                if (root.find(i + 1) != root.end()) {
                    connect(i, i + 1);
                }
            }
        }
        return maxLen;
    }

    void connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            len[root_b] += len[root_a];
            root[root_a] = root[root_b];
            maxLen = max(len[root_b], maxLen);
        }
    }
    int find(int x) {
        if (root[x] == x) {
            return x;
        }
        return root[x] = find(root[x]);
    }

private:
    unordered_map<int, int> root;
    unordered_map<int, int> len; 
    int maxLen = 0;
};