Difficulty: Medium · LeetCode 128

Problem

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

Examples

Constraints

0 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Understanding the problem

A number is a sequence start only if n-1 is NOT in the set. Only count from starts to avoid O(n²). Total while-loop iterations across all starts = n (amortized O(n)).

Intuition

Convert to set for O(1) lookup. For each number, only start counting if it has no predecessor (n-1 not in set). Then count upward. Each element processed at most twice total.

Approach

Put all numbers in a hash set.
For each n: if n-1 not in set (sequence start):
Count up: while n+len in set, increment length.
Update best = max(best, length).
Return best.

Optimized Code — Hash Set O(n)

Pattern: Hash Set for Sequence Detection — Convert to set for O(1) lookup. Start counting only from "sequence beginners" (n-1 not in set). Amortized O(n) because total iterations across all sequences = n.

Python

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

C++

class Solution {
public:
    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+1)) { cur++; len++; }
                best = max(best, len);
            }
        return best;
    }
};

Java

class Solution {
    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+1)) { 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 + 1)) { cur++; len++; }
            best = Math.max(best, len);
        }
    }
    return best;
};