cheetcode

9. Longest Consecutive SequenceMedium

Find the longest run of consecutive integers in an unsorted array.

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Your solution should run in O(n) time.

Examples

Input: nums = [100,4,200,1,3,2]
Output: 4

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints

  • 0 <= nums.length <= 100,000
  • -1,000,000,000 <= nums[i] <= 1,000,000,000