Longest Consecutive Sequence

Problem

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

Constraints:

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

Solution

Approach: Hash Set with Sequence Start Detection

The key insight is to use a hash set for O(1) lookups and only start counting from the beginning of each sequence. We identify sequence starts by checking if num - 1 exists in the set. If it doesn’t, then num is the start of a new sequence.

This approach avoids redundant counting and achieves O(n) time complexity.

Implementation

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        num_set = set(nums)
        longest = 0

        for num in num_set:
            # Only start counting if this is the beginning of a sequence
            if num - 1 not in num_set:
                current_num = num
                current_length = 1

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

                longest = max(longest, current_length)

        return longest

Alternative (More Concise):

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

        for num in num_set:
            # Check if it's the start of a sequence
            if num - 1 not in num_set:
                length = 1
                while num + length in num_set:
                    length += 1
                longest = max(longest, length)

        return longest

Complexity Analysis

Time Complexity: O(n), where n is the length of the array. Although there’s a nested while loop, each number is visited at most twice (once in the outer loop, once in the inner loop when extending a sequence). The set operations (add, lookup) are O(1) on average.
Space Complexity: O(n) for storing all numbers in the hash set.

Key Insights

Sequence Start Detection: The key optimization is checking if num - 1 not in num_set to identify sequence starts. This ensures we only count each sequence once, avoiding redundant work.
Hash Set for O(1) Lookup: Converting the array to a set gives us constant-time lookups for checking consecutive numbers, which is essential for achieving O(n) time.
Avoid Sorting: While sorting would make finding consecutive sequences easier, it would take O(n log n) time, violating the problem’s requirement. The hash set approach is more efficient.
Linear Time Despite Nested Loop: Even though there’s a while loop inside a for loop, the total work is O(n) because each number is processed at most twice - once as a potential sequence start, and once as part of a sequence.
Duplicates Don’t Matter: By converting to a set, we automatically handle duplicates. Duplicates don’t affect the length of consecutive sequences.