Longest Consecutive Sequence — HashSet and the Smart Sequence Start

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.

Constraints:

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

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
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8].

Example 3:
Input:  nums = []
Output: 0

Why This Problem Matters#

Longest Consecutive Sequence explicitly requires O(n) time in its problem statement, which immediately rules out sorting (O(n log n)). This constraint is deliberate — it forces candidates to think about what O(n) data structures can offer. Google and Meta ask this problem because it tests the ability to recognize that a hash set can answer "is n+1 present?" in O(1), enabling a sequence-counting strategy that is invisible without that observation.

The sorting-based solution is tempting and straightforward: sort the array, then scan linearly for consecutive sequences. It runs in O(n log n) and is completely correct. In a real interview at Google or Meta, if you present this as your final answer, you will be asked to do better — and many candidates cannot, because the O(n) solution requires a non-obvious trick.

The trick is: only start counting a consecutive sequence from its beginning. The beginning of a sequence starting at n is identified by the absence of n-1 in the set. If n-1 is not in the set, then n is a sequence start, and you count how far the sequence extends by checking n+1, n+2, etc. Each element participates in exactly one such count (the sequence it belongs to), so the total work across all starting points is O(n).

This problem is also valuable because it teaches "amortized analysis" reasoning: even though the inner while loop appears O(n) per iteration, each element is visited by the inner loop at most once total across all outer loop iterations. This amortized O(1) per element gives O(n) overall — a subtlety that separates strong candidates from weaker ones.

The Core Insight#

Load all elements into a hash set for O(1) membership queries.

For each number n in the set:

• If n - 1 is NOT in the set, then n is the start of a consecutive sequence.
• From n, count how far the sequence extends: check n+1, n+2, ... until the next number is not in the set.
• Record the length of this sequence.

Why this is O(n): Each number n participates in the inner while loop only when it is visited as part of a sequence started by some start. Since each element belongs to exactly one consecutive sequence, and we only start counting from sequence beginnings, each element is visited by the inner loop exactly once. The outer loop also visits each element once. Total work: O(n).

Why not iterate over the original array? The array may have duplicates. Loading into a set deduplicates automatically. Alternatively, iterate over the set (not the array) in the outer loop to avoid redundant processing.

Visual Dry Run#

Input: nums = [100, 4, 200, 1, 3, 2]

Set: {100, 4, 200, 1, 3, 2}

Outer loop — check each number for "sequence start":

Maximum length = 4. The sequence [1, 2, 3, 4] was counted starting from 1.

Notice: when n=1 is identified as a start, the inner loop visits 2, 3, 4 — but 2, 3, 4 are NOT re-processed as starts because n-1 is in the set for each of them. This prevents redundant work.

Solution (Optimal)#

def longestConsecutive(nums: list[int]) -> int:
    if not nums:
        return 0
 
    num_set = set(nums)  # O(1) membership lookup; also deduplicates
    best = 0
 
    for n in num_set:
        # Only start counting from the beginning of a sequence
        if n - 1 not in num_set:
            current = n
            length = 1
 
            while current + 1 in num_set:
                current += 1
                length += 1
 
            best = max(best, length)
 
    return best

var longestConsecutive = function(nums) {
    if (nums.length === 0) return 0;
 
    const numSet = new Set(nums);
    let best = 0;
 
    for (const n of numSet) {
        // Start counting only from sequence beginnings
        if (!numSet.has(n - 1)) {
            let current = n;
            let length = 1;
 
            while (numSet.has(current + 1)) {
                current++;
                length++;
            }
 
            best = Math.max(best, length);
        }
    }
 
    return best;
};

Complexity Analysis

The HashSet solution uses O(n) space for the set. If you are allowed O(n log n) time but need O(1) space, the sort + scan approach is the alternative.

Common Mistakes#

• Not checking n - 1 not in set before starting to count. Without this guard, you count sequences from every element — including middle and end elements. This causes O(n^2) time: element 3 in sequence [1,2,3,4] would count 3,4 (length 2), but you already counted it when processing 1.
• Iterating over the array instead of the set. If nums = [1, 1, 1, 2], iterating over nums processes 1 three times. Use the set to deduplicate.
• Using n - 1 not in nums (array) instead of n - 1 not in num_set. Array membership is O(n); set membership is O(1). This turns your O(n) algorithm into O(n^2).
• Missing the empty array case. max() of an empty list raises a ValueError in Python. Add an early return or initialize best = 0.
• Confusing "consecutive by value" with "consecutive by index." The sequence [1, 2, 3, 4] is consecutive by integer value, not by original array index. The positions in the input array are irrelevant.

Follow-up Questions#

What if the array is sorted? Can you do O(n) time and O(1) space? Yes. Scan the sorted array, tracking the current sequence length. When a gap is found (next element is more than 1 greater than the previous), reset the current length. Handle duplicates by skipping equal adjacent elements.

How does the amortized analysis work for proving O(n) time? Think of each element as having two "tokens": one for the outer loop check and one for the inner while loop. Each element can be "consumed" by the inner loop at most once across all outer iterations. Total tokens consumed = 2n → O(n) total operations.

What if the array can contain duplicates and you need the longest subsequence (not subarray) of consecutive values? The set deduplicates automatically. If you need the subsequence (elements can be non-adjacent), the same approach works — once you have a set, order in the array is irrelevant.

How would you find the actual sequence (not just its length)? When you find a new maximum length, record the starting number and the length. After the full traversal, reconstruct: list(range(best_start, best_start + best_length)).

What if the elements are strings (consecutive by alphabetical order)? Convert each string to its "position" (e.g., ord(ch) for single characters, or a custom encoding for multi-character strings). Apply the same algorithm on the integer positions.

Key Takeaways#

• LC 128 Longest Consecutive Sequence is the canonical "skip starts not at sequence head" hashset trick.
• Insert all numbers into a hash set in O(n).
• Only start counting a streak when num - 1 is NOT in the set — this guarantees you start at the smallest member of each run.
• Inside the streak, walk forward num + 1, num + 2, ... while in the set.
• The amortized complexity is O(n) because each number is touched at most twice (once on outer scan, once during a forward walk).
• Sorting gives O(n log n) but loses the FAANG-favored O(n) target — always present the hashset solution first.
• Same skip-non-heads pattern shows up in island/component counting, graph traversal seeding, and time-series gap detection.

Related Problems#

• LC 128 — Longest Consecutive Sequence: This problem.
• LC 298 — Binary Tree Longest Consecutive Sequence (Premium): Consecutive sequence in a tree path — uses DFS instead of a set.
• LC 549 — Binary Tree Longest Consecutive Sequence II (Premium): Both ascending and descending consecutive paths in a tree.
• LC 674 — Longest Continuous Increasing Subsequence: Consecutive by index (adjacent elements), monotonically increasing — simpler variant.
• LC 300 — Longest Increasing Subsequence: Not restricted to consecutive values — uses DP or binary search.
• LC 1296 — Divide Array in Sets of K Consecutive Numbers: Group elements into sets of k consecutive values — uses a sorted map and the same consecutive-grouping insight.