This is a solution of leetcode 128. Longest Consecutive Sequence.

Analysis

The target here is to find the longest consecutive interval using the integers from a given array and return its length.

Using the brutal force approach, we can sort this array and use a sliding window to find all the consecutive intervals and write down the longest length. The time complexity of array sorting would be normally $O(n\log n)$, and the time complexity of retrieving all the intervals would be $O(n)$. So, the total time complexity would be their sum, $O(n\log n)$.

Instead of listing all the consecutive intervals by sorting the array, we can try to calculate the length of the interval in which an element lays while we retrieve these numbers. We can use a dictionary to store an element as its key and the length of the consecutive interval in which it lays as its value.

Supposes we now have an integer $x$ from the array. If it is already in the dictionary, we don’t need to do anything, we can just move on to the next number. But if it is not in the dictionary, there would be 3 circumstances after we add it to the dictionary,

a) either $x-1$ or $x+1$ is in the dictionary

In this circumstance, adding $x$ into the dictionary can extend the interval ending with $x-1$ or the interval starting with $x+1$, these intervals length should be increased by 1.

b) both $x-1$ and $x+1$ are in the dictionary

In this circumstance, adding $x$ into the dictionary will combine the interval ending with $x-1$ and the interval starting with $x+1$ into a new bigger interval. The length of this new interval should be the sum of these small intervals’ length and also increased by 1.

c) neither $x-1$ nor $x+1$ is in the dictionary

In this circumstance, adding $x$ into the dictionary won’t affect other intervals, so its own length would be 1.

When we update the length of intervals, we need to update both the start and the end of the interval. We don’t need to update other elements in the interval, because when we add new numbers to the dictionary, we only take the end points of the interval into consideration.

Due to we only retrieve each element once, and the time complexity of reading or updating a dictionary is $O(1)$, the total time complexity of this solution would be $O(n)$.

Now, we can write the code.

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = dict()
        
        max_length = 0
        for num in nums:
            if num not in hash_dict:
                left = hash_dict.get(num - 1, 0)
                right = hash_dict.get(num + 1, 0)
                
                cur_length = 1 + left + right
                if cur_length > max_length:
                    max_length = cur_length
                
                hash_dict[num] = cur_length
                hash_dict[num - left] = cur_length
                hash_dict[num + right] = cur_length
                
        return max_length