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 (O(nlog(n)) time, O(1) space) - Sorting

• Sort the array in place O(nlog(n)) and O(1) space.
• Traverse the array and ignore duplicate elements by checking the element in the previous index. O(n)
  • if the current element is the same as the previous one, increment counter.
  • if not, compare the current longest with counter, reset counter to 1.
• After iteration finishes, counter may not have been compared with longest, so we do a compare and return the bigger value.

def longestConsecutive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    nums.sort()
    longest, cur = 1, 1
    for i in xrange(len(nums)):
        if nums[i] != nums[i-1]:
            if nums[i] == nums[i-1] + 1:
                cur += 1
            else:
                longest = max(longest, cur)
                cur = 1
    return max(longest, cur)

Method 2 (O(n) time, O(n) space) - Hashset

• Convert the array into a hashset, which ignores duplicates and provide O(1) lookup. O(n)
• Traverse and find all the elements that are the first number of a consecutive sequence, by checking if a number 1 less than the current number exists in the set.
  • calculate the length of the current sequence by looking up if 1 + current_number exists in the set, then get the difference between the last number and first number.
  • compare previous longest length to the current length.
    • (optional) if current length is longer, return length if its length is greater than half of the array's length.
• return longest.

def longestConsecutive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums = set(nums)
    longest = 0
    half_size = len(nums)/2
    for num in nums:
        if num - 1 not in nums:
            next_num = num + 1
            while next_num in nums:
                next_num += 1
            longest = max(longest, next_num - num)
            # optional
            #count = next_num - num
            #if longest < count:
                #longest = count
                #if longest > half_size:
                    #return longest                
    return longest