Leetcode 128. Longest Consecutive Sequence

Problem

Leetcode 128 - Longest Consecutive Sequence

Example:

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.

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

Approach

We can first get a HashSet of the nums array to remove the duplicates, we then iterate through the set and if we encounter a number that starts the consecutive sequence (num - 1 doesn’t exist in HashSet)

Then we can look for (num + length) and increment length then once loop is finished, we can return the max length

Visualization of the Approach:

nums = [100, 4, 200, 1, 3, 2]
numSet = (100, 4, 200, 1, 3, 2)
maxLength = 0

Since 100-1 doesn't exist we can start the while loop
length = 1
100 + 1 doesn't exist, thus we end loop

maxLength = 1

Since 4-1 exists, we ignore

Since 200-1 doesn't exist we can start the while loop
length = 1
200 + 1 doesn't exist, thus we end loop

maxLength = 1

Since 1-1 doesn't exist, we can start the while loop
length = 1
1 + 1 exists, continue

length = 2
1 + 2 exists, continue

length = 3
1 + 3 exists, continue

length = 4
1 + 4 doesn't exist, thus we end loop

maxLength = 4

Since 3-1 exists, we ignore

Since 2-1 exists, we ignore

Thus, maxLength = 4

Here is the Python code for the solution:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        maxLen = 0
        numSet = set(nums)

        for num in numSet:
            if num-1 not in numSet:
                length = 1

                while num+length in numSet:
                    length += 1
                if maxLen < length:
                    maxLen = length
        
        return maxLen

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$