128 - Longest Consecutive Sequence

Difficulty: Medium | Pattern: Hash Set | Company tags: Google, Amazon, Facebook, Uber

Problem Statement

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 sequence is [1, 2, 3, 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

Approach: Hash Set — O(n)

Key insight: A number is the start of a sequence only if num - 1 is NOT in the set. From each start, count how long the consecutive sequence extends.

This ensures each number is part of exactly one sequence's traversal, keeping the total work O(n).

Algorithm:

1. Put all numbers in a set for O(1) lookups
2. For each number n in nums:
   • Skip if n - 1 is in the set (this isn't a sequence start)
   • Otherwise, count consecutive from n: n, n+1, n+2, ... until not in set
3. Track the maximum count

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    max_len = 0
    
    for n in num_set:
        if n - 1 not in num_set:  # n is the start of a sequence
            current = n
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_len = max(max_len, length)
    
    return max_len

Dry Run

nums = [100, 4, 200, 1, 3, 2] num_set = {100, 4, 200, 1, 3, 2}

n	n-1 in set?	action	sequence found
100	99 not in set	start counting	100 → 101 not in set → length 1
4	3 IS in set	skip	—
200	199 not in set	start counting	200 → 201 not in set → length 1
1	0 not in set	start counting	1 → 2 → 3 → 4 → 5 not in set → length 4
3	2 IS in set	skip	—
2	1 IS in set	skip	—

max_len = 4 ✓

Why Not Sort?

Sorting would give O(n log n). The problem requires O(n). The hash set approach achieves O(n) by doing the "is the next element present?" check in O(1) instead of a binary search.

Edge Cases

• Empty array → 0
• All same values → 1 (duplicates are handled since we use a set)
• Already consecutive → length of array
• Single element → 1

Complexity

• Time: O(n) — despite the nested while loop, each number is visited at most twice (once in the outer for loop, once as part of a sequence)
• Space: O(n) — hash set