Table of contents
Open Table of contents
Problem
Given an unsorted array of integers nums
, return the length of the longest consecutive elements sequence. The algorithm should run in O(n) time complexity.
Example 1:
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.
Example 2:
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
Explanation/Approach
To solve this problem efficiently, we use a hash set to store all elements of the array. Then, for each element, we check if it’s the start of a sequence and calculate the length of this sequence.
Hash Set Approach:
 Store Elements in a Hash Set: Add all elements of
nums
to a hash set for O(1) lookups.  Find the Longest Consecutive Sequence: For each element, check if it’s the start of a sequence (i.e.,
num  1
is not in the set). If it is, count the length of this consecutive sequence.  Update the Maximum Length: Keep track of the maximum length of consecutive sequences found.
Solution: Hash Set
class Solution:
def longestConsecutive(self, nums: List[int]) > int:
num_set = set(nums)
longest_streak = 0
for num in num_set:
# Check if it's the start of a sequence
if num  1 not in num_set:
current_num = num
current_streak = 1
# Count the length of the sequence
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak
Time and Memory Complexity
The time complexity is O(n), assuming a good hash function with O(1) average lookup time. Each element is processed once, and the inner while loop runs for consecutive sequences, which doesn’t exceed the total number of elements. The space complexity is O(n) to store the hash set.
Explanation
The algorithm first inserts all elements into a hash set. Then, it iterates through the set, checking if each number is the start of a new sequence. It then counts the length of the sequence and updates the maximum length found.
Visual Representation
Consider the input nums = [100, 4, 200, 1, 3, 2]
.

Hash Set Creation:
 The hash set contains all unique elements of
nums
.  Set:
{100, 1, 2, 3, 4, 200}
.
 The hash set contains all unique elements of

Identifying Sequences:
 Start at
100
: It’s the first sequence  Since
101
is not in set,longest_streak = 1
 At
1
: Starts a sequence. Sequence is[1, 2, 3, 4]
with length4
.  Other elements are part of this already identified sequence.
 Start at

Result:
 The longest consecutive sequence identified is
[1, 2, 3, 4]
.  The length of this sequence is
4
.
 The longest consecutive sequence identified is