Longest Consecutive Sequence

mediumArrays & Hashing46 stepsJava · Python · C++

Find the length of the longest run of consecutive integers, in O(n). Put all values in a set. A value starts a run only if x - 1 is absent; from each start, count upward while x + len exists. Each number is visited at most twice, so the total is linear.

▶ Watch the animated trace

Traced input: nums = [100, 4, 200, 1, 3, 2] → 4. Original problem: neetcode.io/problems/longest-consecutive-sequence

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

The inner while only runs from run starts, so every value is extended over at most once.

Key idea

Only begin counting at a number whose predecessor is missing; that's the start of a run.
From a start, walk x+1, x+2, … using O(1) set lookups.
Iterating over the set (not the array) skips duplicates for free.

Common mistakes

Starting a count from every number makes it O(n²).
Sorting is O(n log n), which the problem rules out.
Forgetting the empty-array case (answer 0).

Solution

Java

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

Python

def longestConsecutive(nums: List[int]) -> int:
    num_set = set(nums)
    best = 0
    for x in num_set:
        if x - 1 in num_set:
            continue
        length = 1
        while x + length in num_set:
            length += 1
        best = max(best, length)
    return best

C++

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty array No runs; `best` stays 0.	`nums = []`	`0`
Duplicates The set removes the second 1; the run is 0, 1, 2.	`nums = [1, 2, 0, 1]`	`3`
Negative numbers -2 is the start, and the run crosses zero.	`nums = [0, -1, -2, 5]`	`3`
Single element A lone value is a run of length 1.	`nums = [7]`	`1`
Several runs Runs -1..1 (3) and 3..9 (7); the longer wins.	`nums = [9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6]`	`7`