DSA problem
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
A consecutive elements sequence is a set of numbers that, when sorted, form a run of integers that increase by exactly one with no gaps, for example [3, 4, 5, 6]. The numbers do not need to be adjacent in the input array, and duplicates in the input do not extend the sequence length.
You must write an algorithm that runs in O(n) time. This rules out the straightforward approach of sorting the array, which would cost O(n log n).
Examples
Example 1
Input:
nums = [100,4,200,1,3,2]Output:
4Explanation: The longest consecutive elements sequence is [1, 2, 3, 4], which has length 4. The values 100 and 200 are isolated.
Example 2
Input:
nums = [0,3,7,2,5,8,4,6,0,1]Output:
9Explanation: The longest consecutive elements sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has length 9. The duplicate 0 does not add to the length.
Example 3
Input:
nums = []Output:
0Explanation: An empty array contains no sequence, so the length is 0.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.