Algorithm Notes
Summary: Longest Consecutive Sequence — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.
Big-O Guide
Source
"""
LeetCode 128. Longest Consecutive Sequence
Category: Arrays & Hashing
"""
import random
def longest_consecutive(nums: list[int]) -> int:
"""
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Must run in O(n).
"""
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set: # start of a sequence
length = 1
while num + length in num_set:
length += 1
longest = max(longest, length)
return longest
def demo() -> str:
"""Deterministic demo run."""
random.seed(0) # Ensure determinism
sample = [100, 4, 200, 1, 3, 2]
result = longest_consecutive(sample)
return f"Longest consecutive sequence length of {sample} is {result}"