Longest consecutive subsequence

Standard Bar Arrays · Medium O(n) expected · O(n)

Longest Unbroken Session Chain in a Session Log

An analytics store keeps session numbers from many tenants in one unsorted table, and repeated numbers appear when a session is retried. The growth team wants the longest chain of back-to-back session numbers, where the chain does not need to be contiguous in the table. Report the length of that chain.

Input: An array nums of n integers, the session numbers in arbitrary order.

Output: The length of the longest run of consecutive integers present in nums, ignoring duplicates.

Constraints

1 <= n <= 10^5
-10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: {"nums":[100,4,200,1,3,2]}
Output: 4
The numbers 1,2,3,4 form an unbroken chain of four, ignoring their scrambled positions.

Example 2

Input: {"nums":[0,3,7,2,5,8,4,6,0,1]}
Output: 9
Duplicated 0 does not extend the chain, but 0 through 8 are all present for a length of 9.

Solve this in your browser →

Also on LeetCode ↗