Longest Sequence of Consecutive Integers
Given an unsorted list of integers nums, return the length of the longest sequence of consecutive integer values.
The values in a sequence do not need to appear next to each other in the input. Duplicate values do not increase the sequence length.
The solution must run in O(n) time, where n is the number of integers in nums.
Method Signature
int longestConsecutive(List<Integer> nums)
nums is the unsorted list of integers.- Return the length of the longest consecutive sequence.
Constraints
0 ≤ nums.size() ≤ 100,000-1,000,000,000 ≤ nums.get(i) ≤ 1,000,000,000- The required time complexity is
O(n).
Examples
Example 1
longestConsecutive(nums = List.of(8, 3, 5, 2, 6, 4, 20))
Output: 5
Explanation: The longest consecutive sequence is [2, 3, 4, 5, 6], which has a length of 5.
Example 2
longestConsecutive(nums = List.of(12, 10, 11, 10, 15, 14, 13))
Output: 6
Explanation: The values from 10 through 15 form a consecutive sequence of length 6. The duplicate 10 does not increase its length.
Example 3
longestConsecutive(nums = List.of())
Output: 0
Explanation: An empty list contains no consecutive sequence.