Longest Consecutive Sequence

Problem Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Examples

Constraints

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

Only Count From Where a Sequence Actually Starts

Sorting works and gives O(n log n), but the problem demands O(n). The insight: you don’t need elements in order, you need to detect sequence starts. A number n starts a new sequence only if n - 1 is not in the array. If n - 1 exists, then n is part of a sequence that someone else started, and counting from n would double-count.

Put all numbers in a hash set for O(1) lookup. For each number, check if it’s a sequence start. If it is, count forward until the sequence breaks. Every number is the start of at most one sequence, so the total work across all sequences is O(n).

Solution 1: Sort and Scan

Sort the array, then walk through looking for consecutive gaps. Handles duplicates by skipping equal adjacent elements.

import java.util.Arrays;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int longest = 1, current = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) continue; // skip duplicates
            if (nums[i] == nums[i - 1] + 1) {
                current++;
                longest = Math.max(longest, current);
            } else {
                current = 1;
            }
        }
        return longest;
    }
}

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0
        nums = sorted(set(nums))  # deduplicate before scanning
        longest = current = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] + 1:
                current += 1
                longest = max(longest, current)
            else:
                current = 1
        return longest

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        std::sort(nums.begin(), nums.end());
        int longest = 1, current = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) continue;
            current = (nums[i] == nums[i - 1] + 1) ? current + 1 : 1;
            longest = std::max(longest, current);
        }
        return longest;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n). Sorting dominates.
• Space Complexity: O(1) extra (or O(n) if deduplication creates a new array).

Where it breaks: doesn’t meet the O(n) requirement stated in the problem. In an interview this would get you partial credit but not full marks.

Solution 2: Hash Set with Sequence Start Detection

Load all numbers into a set. For each number, only start counting if it’s a sequence start (its predecessor is absent from the set). This ensures each number is counted exactly once across all sequences.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) numSet.add(num);

        int longest = 0;
        for (int num : numSet) {
            // only count from sequence starts to avoid redundant work
            if (!numSet.contains(num - 1)) {
                int length = 1;
                while (numSet.contains(num + length)) length++;
                longest = Math.max(longest, length);
            }
        }
        return longest;
    }
}

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        num_set = set(nums)
        longest = 0

        for num in num_set:
            # only count from sequence starts to avoid redundant work
            if num - 1 not in num_set:
                length = 1
                while num + length in num_set:
                    length += 1
                longest = max(longest, length)

        return longest

#include <vector>
#include <unordered_set>

class Solution {
public:
    int longestConsecutive(std::vector<int>& nums) {
        std::unordered_set<int> numSet(nums.begin(), nums.end());
        int longest = 0;

        for (int num : numSet) {
            // only count from sequence starts to avoid redundant work
            if (!numSet.count(num - 1)) {
                int length = 1;
                while (numSet.count(num + length)) length++;
                longest = std::max(longest, length);
            }
        }
        return longest;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Building the set is O(n). Each number is visited at most twice across all sequence walks: once as a non-start (skipped) and once from inside a sequence walk started elsewhere.
• Space Complexity: O(n). The hash set holds all unique elements.

Where it breaks: worst-case hash collisions degrade set lookup to O(n), making the whole algorithm O(n²). This is a theoretical concern in adversarial inputs; in practice, it doesn’t happen with standard integer inputs.

Why Not Union-Find?

Union-Find can also solve this in near O(n) time. As you process each number, union it with its neighbor if that neighbor exists. The longest sequence corresponds to the largest component. The implementation is significantly more complex for no practical gain here. Hash set wins on simplicity.

Common Mistakes

• Iterating over nums instead of numSet. If nums has duplicates (like [0,0,1,1,2,2]), you’d restart counts from duplicate elements. Iterate over the set to skip duplicates automatically.
• Starting a count from every element. Without the num - 1 not in numSet guard, the inner while loop runs from every element, making the algorithm O(n²) even though it looks like O(n).
• Returning 0 for an empty array before building the set. The loop over the set handles empty input correctly (just never enters), but an explicit early return avoids confusion.

Frequently Asked Questions

Why iterate over the set instead of the original array? To skip duplicates. If the same number appears multiple times in nums, you’d start the same sequence count multiple times without the deduplication a set provides.

Is this actually O(n) or are there hidden quadratic cases? The key insight is that the inner while loop only runs when you’ve found a sequence start. The total number of iterations across all while loops equals the total number of elements in all sequences combined, which is at most n. So the total work is O(n) amortized.

What if all elements are the same, like [7,7,7,7]? The set contains only one element: {7}. It has no predecessor in the set, so you start counting from it. num + 1 = 8 is not in the set, so the sequence length is 1. Correct.

← All Problems