128. Longest Consecutive Sequence

At a Glance

Topic: arrays-hashing
Pattern: Hash Set Sequence
Difficulty: Medium
Companies: Google, Amazon, Meta, Bloomberg, Microsoft
Frequency: High
LeetCode: 128

Problem (one-liner)

Given an unsorted array of integers numbers, return the length of the longest run of consecutive integers in value space (not index order). Algorithm must be O(n) expected time.

Recognition Cues

"Consecutive integers", "longest streak", unsorted array
Sort would be O(n log n) — need set + start only from sequence beginnings

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — for each element, scan x+1, x+2, … — O(n³) worst if naive.
Better — sort, scan runs — O(n log n) time.
Optimal — hash set of all numbers; for each value, if value-1 not in set, walk upward counting — O(n) time / O(n) space.

Optimal Solution

Go

package main

func longestConsecutive(numbers []int) int {
	seen := make(map[int]struct{}, len(numbers))
	for _, value := range numbers {
		seen[value] = struct{}{}
	}
	longest := 0
	for value := range seen {
		if _, hasPrev := seen[value-1]; hasPrev {
			continue
		}
		length := 0
		current := value
		for {
			if _, exists := seen[current]; !exists {
				break
			}
			length++
			current++
		}
		if length > longest {
			longest = length
		}
	}
	return longest
}

JavaScript

function longestConsecutive(numbers) {
	const seen = new Set(numbers);
	let longest = 0;
	for (const value of seen) {
		if (seen.has(value - 1)) {
			continue;
		}
		let length = 0;
		let current = value;
		while (seen.has(current)) {
			length++;
			current++;
		}
		if (length > longest) {
			longest = length;
		}
	}
	return longest;
}