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.

Method 1 HashSets (n time, n space):

• Store every element in a hashset, since it provides O(1) lookup time and we don't care about ignoring duplicate values.
• Traverse the hashset, if an element i is the begining of a sequence, then i-1 shouldn't exist in the hashset.
  • For each begining of a sequence, we find the sequence length by checking if i+1 exists in the hashset.
• Compare each length and find the longest.

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        longest, hset = 0, set()
        for num in nums:
            hset.add(num)
        for num in hset:
            if num - 1 not in hset: # want beginning of a sequence
                count = 1
                while num + 1 in hset:
                    count += 1
                    num += 1
                longest = max(longest, count)
        return longest