LeetCode Longest Consecutive Sequence: Hash Set Trick

Longest Consecutive Sequence (LeetCode 128, Medium) asks for the longest run of consecutive integers in an unsorted array, in O(n). The trick is a hash set plus one clever guard.

The Problem

Given an unsorted array nums, return the length of the longest sequence of consecutive integers. The sequence does not need to be contiguous in the array.

Example:

• Input: nums = [100, 4, 200, 1, 3, 2]
• Output: 4 (the sequence 1, 2, 3, 4)

Brute Force

Sort the array, then scan and count consecutive runs.

def longest_brute(nums):
    if not nums:
        return 0
    nums = sorted(set(nums))
    best = cur = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1] + 1:
            cur += 1
            best = max(best, cur)
        else:
            cur = 1
    return best

O(n log n) due to the sort.

Optimal Solution

Put every number in a hash set. For each value, only start counting if n - 1 is not in the set; that means n is the start of a run. Then walk forward.

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for n in s:
        if n - 1 not in s:
            length = 1
            cur = n
            while cur + 1 in s:
                cur += 1
                length += 1
            best = max(best, length)
    return best

The inner while only runs for true starts, so total work across all iterations is O(n).

Walk Through an Example

nums = [100, 4, 200, 1, 3, 2]. Set: {1, 2, 3, 4, 100, 200}.

• 100: 99 not in set, start. Walk: 101 missing, length 1.
• 4: 3 in set, skip.
• 200: 199 missing, length 1.
• 1: 0 missing, start. Walk to 2, 3, 4. Length 4.
• 3, 2: predecessors present, skip.

Answer: 4.

Edge Cases

• Empty array: return 0.
• Single element: return 1.
• All duplicates like [5,5,5]: deduped by the set, return 1.
• Very large negative and positive mix: the set handles both.
• Long contiguous block where only one number passes the start-of-run guard: still O(n) total.

Complexity Analysis

• Brute force: O(n log n) time, O(n) space.
• Hash set approach: O(n) average time, O(n) space.

The start-of-run guard is essential. Without it, walking forward from every number degenerates to O(n^2) in worst cases like [1,2,3,...,n].

How to Explain It in an Interview

Lead with: “I want O(n), so I’ll trade memory for time using a hash set.” Then explain the start-of-run check. Many candidates write the brute walk-forward loop and don’t see why it’s still linear; the answer is that each value is visited by the inner loop at most once, only when it is part of a run that began at the smallest element. Total inner-loop work sums to n. Mention that average O(1) hash operations rely on a decent hash function, which Python’s set guarantees for ints.

Related Problems

• LeetCode 1 Two Sum (intro to hash maps)
• LeetCode 49 Group Anagrams
• LeetCode 287 Find the Duplicate Number
• LeetCode 1202 Smallest String With Swaps (union-find variant)

Wrap up

This problem is a great demonstration that hash sets can beat sorting when “membership” is the only query you need. The start-of-run guard is the move that takes a naive approach from quadratic to linear and is the detail interviewers listen for.