Problem
Given an unsorted array of integers, find the length of the longest sequence of consecutive elements.The sequence elements must appear consecutively in value, but they do not need to be adjacent in the original array.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [100,4,200,1,3,2] Output
4 1 → 2 → 3 → 4 Solution
A straightforward approach is to sort the array first, which takesO(n log n) time.
Sorting places consecutive numbers next to each other, allowing the longest sequence to be found with a single traversal. Duplicate elements must be ignored so they do not break the sequence.
public int longestConsecutive(int[] nums) {
int n = nums.length;
if (n <= 1) {
return n;
}
Arrays.sort(nums);
int longestSequence = 1;
int currentSequence = 1;
for (int i = 1; i < n; i++) {
// Ignore duplicates.
if (nums[i - 1] == nums[i]) {
continue;
}
// Consecutive element found.
if (nums[i - 1] + 1 == nums[i]) {
currentSequence++;
continue;
}
// Update the longest sequence.
longestSequence = Math.max(longestSequence, currentSequence);
currentSequence = 1;
}
return Math.max(longestSequence, currentSequence);
}
The key observation is that a number should only start a sequence if its previous number does not exist in the set.
For example, in the sequence
1, 2, 3, 4, the number 1 starts the sequence because 0 does not exist. When processing 2, 1 already exists, so 2 cannot be the start of a new sequence. By checking only sequence starting points, each number is processed as part of a sequence only once.
class Solution {
public int longestConsecutive(int[] nums) {
Set elements = new HashSet<>();
for (int num : nums) {
elements.add(num);
}
int longest = 0;
for (int element : elements) {
if (!elements.contains(element - 1)) {
int currentLongest = 1;
while (elements.contains(++element)) {
currentLongest++;
}
longest = Math.max(currentLongest, longest);
}
}
return longest;
}
}
Complexity
Building the HashSet takesO(n) time. During traversal, only numbers that are the beginning of a sequence expand forward. Since each number is processed at most once as part of a sequence, the overall time complexity remains O(n). The HashSet stores the array elements, resulting in an extra space complexity of
O(n).