Leetcode 128 - Longest Consecutive Sequence

Table of contents

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. The algorithm should run in O(n) time complexity.

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

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Explanation/Approach

To solve this problem efficiently, we use a hash set to store all elements of the array. Then, for each element, we check if it’s the start of a sequence and calculate the length of this sequence.

Hash Set Approach:

• Store Elements in a Hash Set: Add all elements of nums to a hash set for O(1) lookups.
• Find the Longest Consecutive Sequence: For each element, check if it’s the start of a sequence (i.e., num - 1 is not in the set). If it is, count the length of this consecutive sequence.
• Update the Maximum Length: Keep track of the maximum length of consecutive sequences found.

Solution: Hash Set

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

        for num in num_set:
            # Check if it's the start of a sequence
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # Count the length of the sequence
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

Time and Memory Complexity

The time complexity is O(n), assuming a good hash function with O(1) average lookup time. Each element is processed once, and the inner while loop runs for consecutive sequences, which doesn’t exceed the total number of elements. The space complexity is O(n) to store the hash set.

Explanation

The algorithm first inserts all elements into a hash set. Then, it iterates through the set, checking if each number is the start of a new sequence. It then counts the length of the sequence and updates the maximum length found.

Visual Representation

Consider the input nums = [100, 4, 200, 1, 3, 2].

1. Hash Set Creation:

   • The hash set contains all unique elements of nums.
   • Set: {100, 1, 2, 3, 4, 200}.

2. Identifying Sequences:

   • Start at 100: It’s the first sequence
   • Since 101 is not in set, longest_streak = 1
   • At 1: Starts a sequence. Sequence is [1, 2, 3, 4] with length 4.
   • Other elements are part of this already identified sequence.

3. Result:

   • The longest consecutive sequence identified is [1, 2, 3, 4].
   • The length of this sequence is 4.