Longest Consecutive Sequence [Medium] — HashSet O(n)

Problem Statement

Given an unsorted integer array, find the length of the longest consecutive elements sequence. Must run in O(n).

Input: [100,4,200,1,3,2] → Output: 4 ([1,2,3,4])

Intuition

Put all numbers in a HashSet. For each number n, only start counting if n-1 is not in the set (meaning n is a sequence start). Count up.

Solutions

C++

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

Java

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

JavaScript

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

Python

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

Complexity

Time: O(n) amortized — each number is visited at most twice
Space: O(n)