Longest Consecutive Sequence
Medium
Array
Hash Table
Union Find
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.
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⁵
  • •-10⁹ <= nums[i] <= 10⁹
Time Complexity
O(n)
Space Complexity
O(n)
14
Case 1
Input: [100,4,200,1,3,2]
Expected: 4
Case 2
Input: [0,3,7,2,5,8,4,6,0,1]
Expected: 9
Case 3
Input: []
Expected: 0