Longest Consecutive Sequence — The Hash Set Trick

Longest Consecutive Sequence (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)

Intuition

The naive solution is to sort the array, then scan and count consecutive runs. That is O(n log n) due to the sort. Can we do O(n)?

The key idea: 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 as long as the next integer is in the set.

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]. With it, each value is visited by the inner loop at most once, because each run is only walked from its smallest element. Total inner-loop work sums to n.

Explanation with 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.

set = { 1, 2, 3, 4, 100, 200 }

n = 100  -> 99 in set? no   START   walk: 101? no   len 1
n =   4  -> 3  in set? YES  skip
n = 200  -> 199 in set? no  START   walk: 201? no   len 1
n =   1  -> 0  in set? no   START
                          walk 1 -> 2 -> 3 -> 4
                          len = 4
n =   3  -> 2  in set? YES  skip
n =   2  -> 1  in set? YES  skip

best = 4

each value v is touched by the inner while-loop
ONLY when the run that contains it was started at
the smallest element of that run.

run: 1 - 2 - 3 - 4   started once (at 1)
     each of {1,2,3,4} visited once -> 4 steps

sum over all runs == n  =>  amortized O(n)

Code

def longestConsecutive(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

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int best = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) {
                int cur = n, length = 1;
                while (set.contains(cur + 1)) { cur++; length++; }
                best = Math.max(best, length);
            }
        }
        return best;
    }
}

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int best = 0;
        for (int n : s) {
            if (!s.count(n - 1)) {
                int cur = n, length = 1;
                while (s.count(cur + 1)) { cur++; length++; }
                best = max(best, length);
            }
        }
        return best;
    }
};

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, the inner walk-forward loop degenerates to O(n^2) on inputs 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.

Related Problems

• Two Sum (intro to hash maps)
• Group Anagrams
• Find the Duplicate Number
• 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.