128. Longest Consecutive Sequence

• Difficulty: Hard

• Topics: Array, Union Find

• Similar Questions:

  • Binary Tree Longest Consecutive Sequence

Problem:

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

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Solutions:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet (nums.begin(), nums.end());

        int ret = 0;

        for (auto num : nums) {
            if (numSet.count(num) > 0) {
                int count = 1;
                count += countToward(numSet, num - 1, true);
                count += countToward(numSet, num + 1, false);
                ret = max(ret, count);
            }
        }

        return ret;
    }

    int countToward(unordered_set<int>& numSet, int num, bool backward) {
        int count = 0;
        while (true) {
            auto it = numSet.find(num);
            if (it == numSet.end()) return count;
            ++count;
            numSet.erase(it);
            if (backward)
                --num;
            else 
                ++num;
        }
    }


};