Longest Consecutive Sequence
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
nums = [100,4,200,1,3,2]
4
The longest consecutive sequence is [1,2,3,4].
nums = [0,3,7,2,5,8,4,6,0,1]
9
The longest consecutive sequence is [0,1,2,3,4,5,6,7,8].
Constraints
- •
0 <= nums.length <= 10^5 - •
-10^9 <= nums[i] <= 10^9
Approaches
For each number, check if num+1, num+2, etc. exist in the array.
def longest_consecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
current = num
while current + 1 in num_set:
current += 1
longest = max(longest, current - num + 1)
return longestSort the array and scan for consecutive sequences.
def longest_consecutive(nums):
if not nums:
return 0
nums = sorted(set(nums))
longest = 1
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 longestOnly start counting from the beginning of a sequence (num-1 not in set).
Diagram
def longest_consecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set:
current = num
while current + 1 in num_set:
current += 1
longest = max(longest, current - num + 1)
return longestComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | For each number, check if num+1, num+2, etc. exist in the array. |
| Sorting | O(n log n) | O(n) | Sort the array and scan for consecutive sequences. |
| Hash Set - Start of Sequence | O(n) | O(n) | Only start counting from the beginning of a sequence (num-1 not in set). |
For each number, check if num+1, num+2, etc. exist in the array.
Sort the array and scan for consecutive sequences.
Only start counting from the beginning of a sequence (num-1 not in set).
Common Mistakes
Not achieving O(n) by starting from each element instead of only sequence starts
Using a sorted array without deduplicating first
Forgetting to handle empty input