Longest Consecutive Sequence

Problem

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.

Examples

The brute-force approach

Sort the array, then scan through it counting consecutive runs. Reset the count whenever a gap appears.

if not nums:
    return 0

nums.sort()    # O(n log n)

best = 1
current = 1

for i in range(1, len(nums)):
    if nums[i] == nums[i-1]:
        continue          # skip duplicates
    if nums[i] == nums[i-1] + 1:
        current += 1
        best = max(best, current)
    else:
        current = 1

return best

Sorting takes O(n log n). The problem is solvable in O(n), sorting throws away the chance to do it faster.

Spotting the pattern

This is a Set problem. The key question to ask yourself:

How do I avoid counting the same sequence over and over from every number inside it?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.