128. Longest Consecutive Sequence

The obvious move — sort the array and scan for runs — is exactly what the problem forbids. It demands $O(n)$, and sorting is $O(n \log n)$. What makes $O(n)$ possible is the same hash-set membership trick behind a lot of array problems, plus one insight about where to start counting.

Question

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.

• Example1

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation:
The longest consecutive elements sequence is [1, 2, 3, 4].
Therefore its length is 4.

• Example2

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9

• Constraints
  • $0 <= nums.length <= 10^5$
  • $-10^9 <= nums[i] <= 10^9$

Algorithm

• HashSet
  • TC: $O(n)$
  • SC: $O(n)$
• Because it requires $O(n)$ complexity,we can not solve the problem by sorting the array first. Sorting takes at least $O(n log n)$ time.
• We can use a HashSetto check if a number exists in $O(1)$. By only starting a count from sequence heads (num - 1 not in set), the total iterations remain $O(n)$.

Answer

// TC: O(n)
// SC: O(n)
public int longestConsecutive(int[] nums) {
    if (nums == null || nums.length == 0) return 0;

    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) numSet.add(num);

    int longest = 0;
    for (int num : numSet) {
        // Only start counting from the beginning of a sequence
        if (!numSet.contains(num - 1)) {
            int currentNum = num;
            int length = 1;
            while (numSet.contains(currentNum + 1)) {
                currentNum++;
                length++;
            }
            longest = Math.max(longest, length);
        }
    }
    return longest;
}

Explain

Why num - 1 check makes it O(n), not O(n²)

Although there are two loops (outer for + inner while), the num - 1 check ensures each number is visited by the while loop at most once.

nums = [1, 2, 3, 4, 100]

Without num - 1 check — every number starts its own count:

num=1 → while: 2, 3, 4  (while x 3 times)
num=2 → while: 3, 4     (while x 2 times)
num=3 → while: 4        (while x 1 time)
num=4 → while: nothing  (0 times)
num=100 → while: nothing (0 times)

total while iterations = 6  → O(n²)

With num - 1 check — only sequence heads start counting:

num=1   → 0 not in set → start! while: 2, 3, 4 (3 times)
num=2   → 1 in set → skip
num=3   → 2 in set → skip
num=4   → 3 in set → skip
num=100 → 99 not in set → start! while: nothing (0 times)

total while iterations = 3  → O(n)

Key Insight

Each number is counted by the while loop exactly once — at its sequence head.
Even with two loops, the total number of iterations across all while executions is at most n → O(n).

Two details that keep it honest

Dumping nums into a set first does double duty: it gives $O(1)$ membership checks and collapses duplicates, so the second example’s repeated 0 can’t inflate the count or start a second walk. And the empty-input guard up front matters — without it, the longest = 0 seed is still correct, but returning early on an empty array keeps the intent obvious. The seed of 0 (not 1) is deliberate too: an empty array has no sequence, so the answer should be 0, not a phantom length-1 run.

References

• https://leetcode.com/problems/longest-consecutive-sequence/