Problem

At Stripe, event IDs may arrive out of order. Given an unsorted array of integers nums, return the length of the longest sequence of consecutive integers.

A consecutive sequence contains values that differ by 1, and the elements do not need to appear next to each other in the input array.

Formal Specification

• Input: nums, a list of integers
• Output: An integer representing the maximum length of any consecutive sequence in nums

Examples

Example 1

• Input: nums = [100, 4, 200, 1, 3, 2]
• Output: 4
• Explanation: The longest consecutive sequence is [1, 2, 3, 4].

Example 2

• Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
• Output: 9
• Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Duplicate values do not extend the sequence.

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• Your solution should run in O(n) average time

Notes

• The input may contain duplicates.
• An empty array should return 0.