MediumLeetCode #128Arrays & Hashing
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.
Constraints
0 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9
Examples
Input: nums = [100,4,200,1,3,2]
Output: 4
The longest consecutive sequence is [1, 2, 3, 4].
Solution Approach
Use a HashSet for O(1) lookup. For each number, check if it is the start of a sequence (num-1 not in set), then count consecutive numbers.
Implementation
def longestConsecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set:
current = num
streak = 1
while current + 1 in num_set:
current += 1
streak += 1
longest = max(longest, streak)
return longestComplexity Analysis
Time Complexity
O(n)Space Complexity
O(n)Complexity
Time:O(n)
Space:O(n)
Hints
- 1.How do you identify the start of a sequence?
- 2.Use a set for O(1) lookups
- 3.Only start counting from sequence beginnings
Asked at
Google