Problem Statement
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.
Approach
Use a hash set. For each number, check if it is the start of a sequence (num-1 not in set), then count consecutive numbers.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Examples
Example 1
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: Longest consecutive sequence is [1,2,3,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
Loading...
Sign in to run your code...
Asked by companies:
GoogleAmazonFacebookMicrosoft