Longest Consecutive Sequence

Find the length of the longest run of consecutive values in an unsorted array.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Consecutive Sequence: Only values without a predecessor start a run; then advance one value at a time.

Input and goalFind the length of the longest run of consecutive values in an unsorted array.

Build the membership setDeduplicate nums into {1,2,3,4,100,200}; best starts at 0. Sorted display does not change set membership or the answer.

next candidate 11021324310042005

examplenums = [100, 4, 200, 1, 3, 2]; set displayed in sorted ordermapLabelscalar state and membership queryset{1,2,3,4,100,200}

scalar state and membership querybest0

Recognize it

The input is unsorted and asks for consecutive integer values, not consecutive positions, while near-linear time rules out sorting as the intended mechanism.

Keep true

A run is expanded only from its unique smallest value, identified by missing predecessor; best is the maximum completed run length seen so far.

Reuse it

Before expanding a component, find a unique boundary that only one member can satisfy; this avoids duplicate work in runs, intervals, and component scans.

Pattern: Set.

Simple idea: Start counting only when value - 1 is missing. That means the value is the start of a run. Each run is counted once.

def longest_consecutive(nums: list[int]) -> int:
   values = set(nums)
   best = 0

   for start in values:
      if start - 1 in values:
         continue

      end = start
      while end + 1 in values:
         end += 1
      best = max(best, end - start + 1)

   return best

Cost: $O(n)$ average time and $O(n)$ space.