Given an unsorted integer array arr, return the length of the longest sequence of consecutive integers present in arr. The sequence does not need to be contiguous in the array. The algorithm must run in O(n) time.
Example 1
Input: [10, 11, 12, 15, 16, 17, 18]
Output: 4
Explanation: The longest consecutive sequence is [15, 16, 17, 18], length 4.
Example 2
Input: [5, 2, 3, 1, 4]
Output: 5
Explanation: The longest consecutive sequence is [1, 2, 3, 4, 5], length 5.
Example 3
Input: [20, 21, 23, 24, 25, 22]
Output: 6
Explanation: The longest consecutive sequence is [20, 21, 22, 23, 24, 25], length 6.
Constraints
Case 1
Input: [30, 31, 32, 40, 41, 42, 43, 44]
Expected: 5
Case 2
Input: [1, 3, 5, 7, 9]
Expected: 1
Case 3
Input: [100, 101, 102, 104, 105, 106, 103]
Expected: 7
Case 4
Input: [-2, -1, 0, 1, 2, 3, 10]
Expected: 6
Case 5
Input: [50]
Expected: 1