Longest Consecutive Sequence — HashSet O(n) with Amortized Analysis [LC 128]

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

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

Input:  nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Why This Problem Matters#

LeetCode 128 appears frequently at Google, Amazon, and Meta because it tests a subtle skill: rejecting the obvious O(n log n) sorting approach and finding a genuinely O(n) solution. The problem explicitly requires O(n) time, which rules out every comparison-based sort.

What makes it interesting is that the optimal solution uses a nested loop that looks like O(n²) at first glance. Understanding why it is actually O(n) requires amortized analysis — the kind of reasoning that separates candidates who memorize solutions from those who truly understand algorithmic complexity. This is exactly what FAANG interviewers probe.

The Core Insight#

Only start counting a consecutive sequence when num - 1 is NOT in the set.

If num - 1 exists in the set, then num is not the start of a sequence — it's a middle or end element. Starting a count from num would double-count work already covered when processing the actual start.

This single condition is the entire algorithm:

1. Put all numbers in a HashSet for O(1) lookup
2. Iterate over each number
3. If num - 1 is in the set, skip — this is not a sequence start
4. Otherwise count forward: check num+1, num+2, ... until the chain breaks
5. Track the maximum length seen

Why this is O(n): Each number is visited at most twice — once as a potential start (outer loop) and at most once inside an inner while loop for exactly one sequence. Total inner while iterations across all outer iterations is bounded by n. This is amortized O(n).

Visual Dry Run#

Input: [100, 4, 200, 1, 3, 2], set = {100, 4, 200, 1, 3, 2}

Result: max(1, 1, 4) = 4. Elements 2, 3, 4 consumed inside the inner loop for start=1 — never triggered a new outer count.

Solution (Optimal)#

class Solution:
    def longestConsecutive(self, nums):
        num_set = set(nums)
        best = 0
        for n in num_set:
            if n - 1 not in num_set:   # only start from sequence beginning
                cur = n
                length = 1
                while cur + 1 in num_set:
                    cur += 1
                    length += 1
                best = max(best, length)
        return best

var longestConsecutive = function(nums) {
    const numSet = new Set(nums);
    let best = 0;
    for (const n of numSet) {
        if (!numSet.has(n - 1)) {
            let cur = n;
            let length = 1;
            while (numSet.has(cur + 1)) {
                cur++;
                length++;
            }
            best = Math.max(best, length);
        }
    }
    return best;
};

Time: O(n) — each element pushed once, consumed by inner loop at most once Space: O(n) — HashSet stores all distinct elements

Common Mistakes#

• Sorting instead of using a HashSet — produces correct output but O(n log n), violating the constraint
• Starting a count from every element without the start condition — degrades to O(n²) worst case
• Building the set incrementally while iterating — later elements haven't been added yet, producing wrong results
• Iterating over nums instead of the set — duplicates cause multiple false sequence starts
• Confusing the O(n) amortized argument — not realizing that each element participates in exactly one inner while traversal

Interview Tips#

• Explain the O(n) constraint rules out sorting before proposing the HashSet approach
• State the start condition clearly: "we only count from numbers where num-1 is absent"
• Give the amortized argument: total inner while iterations across all outer iterations is at most n
• Mention that iterating over the set (not the original array) handles duplicates automatically
• Draw the dry run: visually show that 2, 3, 4 are consumed inside start=1's inner loop

Follow-up Questions#

• What if the input is a data stream — numbers arriving one at a time? (HashMap where each key maps to its sequence length, merge on insertion)
• What if the consecutive sequence must be strictly increasing by exactly 1? (Already the case — this is the problem)
• What about a 2D grid with consecutive cell values? (Graph DFS/BFS from cells where value-1 has no neighbor)
• Can you do it with O(1) extra space? (Sorting works in-place at O(n log n) time — tradeoff)
• How would you find the actual sequence, not just its length? (Track start position, reconstruct from start to start+length-1)

Key Takeaways#

• LeetCode 128 is asked at Google, Amazon, and Meta; explicitly requires O(n) — sorting is not acceptable
• HashSet gives O(1) membership testing without the O(n log n) cost of sorting
• Only start counting from numbers where num - 1 is absent — this is the entire algorithm's key condition
• Each number is visited at most twice across the whole algorithm — once in outer loop, at most once in inner loop
• This gives amortized O(n) time despite the nested loop structure — no element is ever double-counted
• Iterate over the set (not the original array) to handle duplicates automatically
• The start-condition pattern generalizes: "only process from the true beginning" appears in many O(n) algorithms