deepSWE.io

Longest Consecutive Sequence

Hashing

MediumLeetCode #128

25 min

Problem Statement

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

Example

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.

Solution (Hash Set)

We can solve this efficiently by using a hash set to store all the numbers. This allows for O(1) lookups. Then, we iterate through the numbers and for each number, we check if it is the start of a sequence.

Algorithm Steps

Create a hash set from the input array for quick lookups.
Initialize a variable `longest` to 0.
Iterate through each number in the set.
For each number, check if `num - 1` exists in the set. If it doesn't, this number is the start of a new potential sequence.
If it is a start of a sequence, start counting the length of this sequence by checking for `num + 1`, `num + 2`, and so on, in the set.
Update `longest` with the maximum sequence length found so far.
After checking all numbers, `longest` will hold the length of the longest consecutive sequence.

Input Array:

Number Set

100

200

Longest Sequence

Current Length: 0

Create a set from the input array for O(1) lookups.

Longest Consecutive Sequence Solution


class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        numSet = set(nums)
        longest = 0
        
        for n in numSet:
            # check if its the start of a sequence
            if (n - 1) not in numSet:
                length = 1
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        
        return longest