Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence (a run of consecutive integers, not necessarily contiguous in the array). You must write an algorithm that runs in O(n) time.

Input / output

• Input: nums: integer[] (unsorted, may contain duplicates)
• Output: integer, the length of the longest run of consecutive values

Examples

1. nums = [100, 4, 200, 1, 3, 2] returns 4 because the longest run is [1, 2, 3, 4].
2. nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] returns 9 because the longest run is [0, 1, 2, 3, 4, 5, 6, 7, 8].
3. nums = [] returns 0.

Constraints

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

Follow-up Why does only starting a run when n - 1 is absent from the set guarantee O(n) total work instead of O(n^2)?