128. Longest Consecutive Sequence

Quick Identifier

• Topic: arrays-hashing
• Pattern: Hash Set (Sequence Building)
• Hint: Throw everything into a Hash Set. Then, to avoid $O(N^2)$ repeated work, only start counting a sequence if the current number is the absolute beginning of a sequence. How do you know it's the beginning? Because currentNumber - 1 doesn't exist in the set.
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Bloomberg, Microsoft
• LeetCode: 128

Quick Sights

• Time Complexity: O(n). Building the set takes $O(n)$. Then, although there is a while loop inside a for loop, the inner loop only runs for numbers that are the start of a sequence. Thus, every number is visited at most twice (once in the outer loop, once in the inner loop). Total time is $O(n)$.
• Space Complexity: O(n). The Hash Set stores all unique numbers from the array.
• Core Mechanism: Convert the array to a Hash Set for $O(1)$ lookups. Iterate through the set. For each num, check if num - 1 exists.
  • If it does exist, skip it. This num is just a middle piece of some sequence.
  • If it doesn't exist, this num is the start of a sequence. Enter a while loop, checking for num + 1, num + 2, etc., keeping a length tally. Keep track of the maximum length seen.

Concept Explanation

As a senior engineer, the strict constraint here is O(n) time. The moment you see that constraint on an unsorted array problem looking for sequences or pairs, your brain must immediately ban the .sort() function ($O(n \log n)$) and reach for a Hash Set.

1. The Brute Force Trap: If you throw everything into a set, and then for every number, you count upward as high as you can go, you will recount the same sequences over and over. If the array is [1, 2, 3, 4], checking 1 counts to 4. Checking 2 counts to 4. Checking 3 counts to 4. That degrades to $O(N^2)$ in the worst case (a single massive sequence).
2. The "Start of Sequence" Invariant: How do we prevent recounting? We just need to identify the "Head" of the sequence.
   • Is 2 the head? No, because 1 is in the set.
   • Is 3 the head? No, because 2 is in the set.
   • Is 1 the head? Yes, because 0 is not in the set.
3. The Pruning: By adding a simple if (!set.has(num - 1)) check, we instantly prune all middle-of-sequence calculations. We only ever trigger the inner while loop from the absolute bottom of a chain, guaranteeing strict $O(N)$ linear time.

Diagram

This flowchart outlines the intelligent Hash Set pruning logic.

Study Pattern (SDE3+)

• 0–3 min: Immediately point out the O(n) constraint and rule out sorting. Introduce the Hash Set. Crucially, explain why the naive Hash Set approach is $O(n^2)$ and how the !set.has(num - 1) check mathematically collapses the time complexity back to amortized $O(n)$.
• Implementation pass: In languages like Go without a native Set, use a map[int]struct{} for zero-memory boolean tracking. Be sure to iterate over the Set (or keys of the map), not the original array, to naturally skip duplicate numbers right out of the gate.
• 5 min extension: What if the interviewer says, "Good, but now do it in $O(1)$ space"? The only way to do it in $O(1)$ space is to sort the array, which takes $O(n \log n)$ time. You would explain the trade-off: you can't have both $O(n)$ time and $O(1)$ space for this specific problem unless the numbers are bounded within a very small range (allowing a fixed-size boolean array).

Approaches

• Sorting — Sort the array, then iterate through to find the longest streak. Time: $O(n \log n)$, Space: $O(1)$ (or $O(n)$ depending on sort). Suboptimal due to time constraint.
• Naive Hash Set — Throw in a set, count upward from every element. Time: $O(n^2)$, Space: $O(n)$. Suboptimal.
• Intelligent Hash Set — Throw in a set, only count upward if num-1 is missing. Time: $O(n)$, Space: $O(n)$. (Always pick this)

Optimal Solution

Go

func longestConsecutive(nums []int) int {
	// Create a set using a map with an empty struct (zero memory allocation)
	numSet := make(map[int]struct{}, len(nums))
	for _, n := range nums {
		numSet[n] = struct{}{}
	}

	longestSeq := 0

	// Iterate through the unique numbers in the set
	for num := range numSet {
		// Pruning: Only start counting if this number is the start of a sequence
		if _, hasPrev := numSet[num-1]; !hasPrev {
			currentNum := num
			currentStreak := 1

			// Walk upward as long as the consecutive number exists
			for {
				if _, hasNext := numSet[currentNum+1]; hasNext {
					currentNum++
					currentStreak++
				} else {
					break
				}
			}

			// Update global max
			if currentStreak > longestSeq {
				longestSeq = currentStreak
			}
		}
	}

	return longestSeq
}

JavaScript

function longestConsecutive(nums) {
	// Load all numbers into a Hash Set for O(1) lookups
	const numSet = new Set(nums);
	let longestSeq = 0;

	for (const num of numSet) {
		// Pruning: Only start counting if 'num' is the start of a sequence
		// (Meaning the number just below it doesn't exist)
		if (!numSet.has(num - 1)) {
			let currentNum = num;
			let currentStreak = 1;

			// Walk upward through the consecutive sequence
			while (numSet.has(currentNum + 1)) {
				currentNum++;
				currentStreak++;
			}

			// Update global max
			longestSeq = Math.max(longestSeq, currentStreak);
		}
	}

	return longestSeq;
}

Walkthrough

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

Output: 4 (The sequence [1, 2, 3, 4]).

Edge Cases

• Empty array. Correctly bypasses the loops and returns 0.
• Array with duplicates (e.g., [1, 2, 0, 1]). The Set automatically collapses duplicates, so the algorithm perfectly counts the sequence [0, 1, 2] without being thrown off by the extra 1.

Pitfalls

• Iterating over the original nums array instead of the numSet. If the array is [1, 1, 1, 1, 1, 2], and you iterate over nums, you will trigger the start-of-sequence logic for the 1 five different times! Iterating over the Set guarantees you only check 1 once.
• Misunderstanding the $O(n)$ proof. A nested loop usually means $O(n^2)$, but because the if statement ensures the while loop only runs exactly once per sequence, the total number of operations inside the while loop across the entire execution of the program will never exceed $N$. $O(N + N) = O(N)$.

Similar Problems

• 217. Contains Duplicate — Foundational Hash Set usage.
• 049. Group Anagrams — Hash Map state grouping.
• Number of Connected Components in an Undirected Graph — The graph theory analogue to finding isolated "sequences" (components).

Mind-Map Tags

#arrays #hashset #sequence-building #amortized-on #pruning