Longest Consecutive Sequence

LeetCode 128: Longest Consecutive Sequence Solution & Explanation

Problem Overview

TL;DR: Store all values in a hash set, begin counting only from values with no predecessor, and extend each sequence by checking whether successive values exist.

For LeetCode 128: Longest Consecutive Sequence, return the length of the longest sequence of distinct integers that increase by exactly 1. The values do not need to be adjacent in the input array, and duplicate values should be counted only once.

The required LeetCode 128 Solution must run in expected O(n) time, where n is the number of elements in nums. This makes direct sorting unsuitable because sorting requires O(n log n) time.

This is a popular interview question because it tests hash-set membership checks, duplicate handling, and the ability to avoid repeated work. The optimal solution for interviews identifies the beginning of each sequence before scanning forward.

Brute Force Approach for Longest Consecutive Sequence

A direct approach is to examine every value as a possible starting point:

1. Select a value from nums.
2. Check whether value + 1 exists anywhere in the array.
3. Continue searching for value + 2, value + 3, and so on.
4. Stop when the next value does not exist.
5. Track the longest sequence found.

Because the array is unsorted, each existence check may scan the entire array.

Naive Pseudocode

longest = 0

for each value in nums:
    length = 1
    nextValue = value + 1

    while nextValue exists in nums:
        length += 1
        nextValue += 1

    longest = max(longest, length)

return longest

If the array contains a long consecutive range, the algorithm repeatedly scans nums for many successive values. For example, a range of n consecutive values can cause approximately n searches, each taking O(n) time.

Therefore:

• Time complexity: O(n^2) in the worst case
• Space complexity: O(1) additional space, excluding the input

With n up to 100,000, this approach can require billions of comparisons and will likely result in Time Limit Exceeded.

Algorithm Strategy: Array/Matrix Manipulation Patterns

1. Insert every element of nums into a hash set named values.
2. Initialize longest to 0.
3. Iterate through each distinct value in the set.
4. Check whether value - 1 exists:
   • If it exists, skip this value because it is not a sequence start.
   • If it does not exist, begin a new sequence from value.
5. Starting with a length of 1, check whether value + length exists in the set.
6. Increase the length while consecutive values are present.
7. Update longest with the largest sequence length found.
8. Return longest.

The hash set enforces constant-time expected existence checks, while the predecessor condition prevents the same sequence from being expanded repeatedly.

Execution Flow

Consider the values:

[14, 9, 11, 10, 13, 15, 15, 2]

After hashing, the distinct values are:

{2, 9, 10, 11, 13, 14, 15}

The execution proceeds as follows:

1. For 2:

   • 1 is absent, so 2 is a sequence start.
   • 3 is absent, so the sequence length is 1.
   • longest becomes 1.

2. For 9:

   • 8 is absent, so 9 is a sequence start.
   • 10 and 11 exist.
   • 12 is absent.
   • The sequence length is 3, so longest becomes 3.

3. For 10:

   • 9 exists.
   • Skip 10; it is already covered by the sequence beginning at 9.

4. For 11:

   • 10 exists.
   • Skip 11.

5. For 13:

   • 12 is absent, so 13 is a sequence start.
   • 14 and 15 exist.
   • 16 is absent.
   • The sequence length is 3.

6. For 14 and 15:

   • Their predecessors exist.
   • Both values are skipped.

7. Return 3.

The iteration order of a hash set is unspecified, but the result is independent of that order because every sequence is expanded only from its smallest value.

Proof of Correctness

We prove that the algorithm returns the length of the longest consecutive sequence.

Claim 1: Every sequence is expanded from its smallest value

Let a consecutive sequence have smallest value s. By definition, s - 1 is not part of that sequence. If s - 1 existed anywhere in the set, then s would not be the smallest value of its maximal consecutive sequence. Therefore, the algorithm identifies s as a valid sequence start.

Claim 2: Starting from a valid sequence start counts the entire sequence

When the algorithm starts at s, it checks:

s + 1, s + 2, s + 3, ...

It increments the length for every value found in the set. Since the sequence contains exactly consecutive values, the loop stops at the first missing value. Thus, the computed length is exactly the length of the sequence beginning at s.

Claim 3: No sequence is counted multiple times

Any value after the smallest value of a sequence has an immediate predecessor in the set. The algorithm skips such values because they fail the condition:

value - 1 not in values

Therefore, each maximal consecutive sequence is expanded exactly once.

Conclusion

Every maximal consecutive sequence is counted exactly once, and its exact length is compared with longest. Therefore, the algorithm returns the length of the longest consecutive sequence.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 202: Happy Number
• LeetCode 349: Intersection of Two Arrays
• LeetCode 219: Contains Duplicate II
• LeetCode 3: Longest Substring Without Repeating Characters

Each problem uses hashing to record values or states and perform efficient existence checks. Happy Number detects previously seen transformations, Intersection of Two Arrays checks whether values occur in another collection, Contains Duplicate II tracks recent positions, and Longest Substring Without Repeating Characters tracks characters currently represented in a window. For Longest Consecutive Sequence, the same subpattern is applied to integer existence checks and sequence-boundary detection.

Reference Implementation

C++ Solution for LeetCode 128

1class Solution {
2public:
3    int longestConsecutive(vector<int>& nums) {
4        unordered_set<int> values(nums.begin(), nums.end());
5        int longest = 0;
6
7        for (int value : values) {
8            if (values.find(value - 1) != values.end()) {
9                continue;
10            }
11
12            int length = 1;
13            while (values.find(value + length) != values.end()) {
14                ++length;
15            }
16            longest = max(longest, length);
17        }
18
19        return longest;
20    }
21};

The unordered_set removes duplicates and supports expected O(1) membership checks. The continue statement ensures that only sequence starts perform forward expansion.

Java Solution for LeetCode 128

1class Solution {
2    public int longestConsecutive(int[] nums) {
3        java.util.Set<Integer> values = new java.util.HashSet<>();
4        for (int num : nums) {
5            values.add(num);
6        }
7
8        int longest = 0;
9
10        for (int value : values) {
11            if (!values.contains(value - 1)) {
12                int length = 1;
13                while (values.contains(value + length)) {
14                    length++;
15                }
16                longest = Math.max(longest, length);
17            }
18        }
19
20        return longest;
21    }
22}

The Java implementation follows the same boundary-detection invariant. A value is expanded only when its predecessor is absent from the HashSet.

Python Solution for LeetCode 128

1from typing import List, Optional
2
3
4class Solution:
5    def longestConsecutive(self, nums: List[int]) -> int:
6        values = set(nums)
7        longest = 0
8
9        for value in values:
10            if value - 1 not in values:
11                length = 1
12                while value + length in values:
13                    length += 1
14                longest = max(longest, length)
15
16        return longest

Python's set automatically removes duplicates and provides expected constant-time membership checks. The empty input case works naturally because the set is empty and longest remains 0.