Longest Consecutive Sequence

Approach Summary

Put all numbers in a set. For each number that has no predecessor (n-1 not in set), count consecutive streak forward.

Full Solution & Approach

The brute force checks each element and extends a run while consecutive values exist — but doing that naively for every element is O(n²). The insight: only start counting a run at the beginning of a run. Convert the array to a set for O(1) membership tests. For each number n, if n - 1 is not in the set, then n is the start of a consecutive run — count how many steps you can take while n + length is in the set. Every number belongs to exactly one run, and only the first element of each run triggers a scan, so the total work across all runs is O(n): each element is visited once as part of one run's scan plus once in the outer loop. This avoids the sorting-based O(n log n) solution entirely.

Each element is examined a constant number of times — once in the outer loop and at most once inside a run scan — so O(n) time. A set of n elements gives O(n) space.

Solution Code

Solution

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for n in num_set:
        if n - 1 not in num_set:
            length = 1
            while n + length in num_set:
                length += 1
            best = max(best, length)
    return best

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (!set.has(n - 1)) {
      let length = 1;
      while (set.has(n + length)) length++;
      best = Math.max(best, length);
    }
  }
  return best;
}

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int best = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {
            int length = 1;
            while (set.contains(n + length)) length++;
            best = Math.max(best, length);
        }
    }
    return best;
}

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> set(nums.begin(), nums.end());
    int best = 0;
    for (int n : set) {
        if (!set.count(n - 1)) {
            int length = 1;
            while (set.count(n + length)) length++;
            best = max(best, length);
        }
    }
    return best;
}

Edge Cases to Watch

Empty array — return 0
All elements identical — the run has length 1
Negative numbers — runs work on any integers
The full range present, e.g. 1..100000 — each element scanned once by the run logic

How to Recognize This Pattern

Longest consecutive streak
O(n) required

Complexity Analysis

Time Complexity

O(n)

Space Complexity