LeetCode #128 Medium

Longest Consecutive Sequence

Given an unsorted array, return the length of the longest run of consecutive integers (in O(n) time).

arrayhash-setunion-find

02

Intuition

Sorting would solve it but costs O(n log n). Instead, dump everything into a set for O(1) membership. Only start counting a run from its true beginning — a number whose predecessor is absent — so each run is walked exactly once.

How to spot this pattern

A hash set turns "is n+1 present?" into O(1), but the real insight is the n - 1 not in s guard: it starts a walk only from a sequence's first element. That single check is what keeps the total work linear despite the inner while loop — every element is walked over at most once across the whole run.

03

Approach

1

Sorting solves it — but it's too slow

If you sort, consecutive numbers line up and you can scan for the longest run. Correct, but sorting is O(n log n), and this problem explicitly wants O(n). So we need the grouping benefit of sorting without paying to sort. A hash set gives us O(1) membership checks, which is the tool that replaces sorting here.

2

Only walk a run from its true beginning

Drop every number into a set. The danger is double-counting: if we tried to grow a run from every number, a length-k run would be walked k times, ballooning to O(n²). The fix is a guard — a number n is only the start of a run if n − 1 is absent from the set. That condition is true for exactly one number per run, so each run is discovered once and walked once.

3

Extend forward and total it up

From a confirmed start n, keep checking n+1, n+2, … in the set, counting length until the chain breaks, and track the maximum. Because the expensive walking only fires at run-starts, the combined length of all walks is at most n — so even with the outer loop, total work is O(n). Duplicates collapse harmlessly in the set; an empty array yields 0.

04

Solution & live demo

▶1class Solution:
▶2    def longestConsecutive(self, nums):
▶3        s = set(nums)
▶4        best = 0
▶5        for n in s:
▶6            if n - 1 not in s:
▶7                length = 1
▶8                while n + length in s:
▶9                    length += 1
▶10                best = max(best, length)
▶11        return best

05

Common pitfalls

Walking from every element

✗ Wrong

for n in s:
    length = 1
    while n + length in s:
        length += 1

✓ Right

for n in s:
    if n - 1 not in s:
        length = 1
        while n + length in s:
            length += 1

Without the guard, a run of length k is re-walked from each of its k members, giving O(n²) on a single long sequence. Starting only where a run begins means each element is visited once by exactly one walk.

Sorting first

✗ Wrong

nums.sort()
# then scan for runs

✓ Right

s = set(nums)

Sorting is correct but O(n log n), and the problem asks for O(n). The set gives constant-time membership, which is the only ordering information the algorithm actually needs.

Iterating the list instead of the set

✗ Wrong

for n in nums:

✓ Right

for n in s:

Duplicates in the input cause the same run to be walked repeatedly, reintroducing the quadratic blowup the guard was meant to prevent. Iterating the set visits each distinct value once.

06

Edge cases

Duplicates, e.g. [1,2,2,3]

The set collapses duplicates, so a repeated value neither lengthens nor restarts a run.

Empty array

The loop never runs; best stays 0.

Scattered singletons

Each lone number is its own run of length 1 because its neighbor is absent.

07

Complexity

Time

O(n)

Space

O(n)

Set build is O(n); each element walked at most once as part of one run.