Longest Consecutive Sequence

Problem statement

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

You must write an algorithm that runs in O(n) time.

Example 1:

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

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Solution

The most obvious solution would be sorting it first and count from start but that would be $O(nlogn)$ not $O(n)$.

The algorithm for this is simple, we first need to find the start (initial point) to start this array.

Once we found the start, we increment until we can't to count the longest length.

We skip all the element that's not the start (i.e: There is 1 element smaller than it in the array) so that we don't start over the duplicated one.

Implentation

class App:
    def longestConsecutive(self, nums: List[int]) -> int:
        uniqueNumList = set(nums)
        
        result = 0
        for num in nums:
            if not self.isStartNumber(num, uniqueNumList): continue
            
            currNumber = num + 1
            length = 1
            while currNumber in uniqueNumList:
                length += 1
                currNumber += 1
            
            result = max(length, result)

        return result

    def isStartNumber(self, num: int, uniqueNumList: Set) -> bool:
        return num - 1 not in uniqueNumList

Time Complexity: $O(n)$

• Because we only visit an element once
  Space Complexity: $O(n)$