🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires finding the length of the longest consecutive elements sequence in an unsorted array. A naive approach would involve sorting the array, which would take O(n log n) time. However, we need an O(n) time complexity solution. By using a set to store the elements, we can achieve O(1) average time complexity for lookups, enabling an efficient way to find consecutive sequences.
Approach
- Convert the array to a set: This allows for O(1) average time complexity for element lookups.
- Iterate through the array:
For each number in the array:
- Check if it is the start of a sequence by ensuring that the number just before it (
num - 1
) is not in the set. - If it is the start of a sequence, use a while loop to count the length of the sequence by incrementing the current number and checking if the incremented number is in the set. - Keep track of the maximum sequence length found. - Return the maximum sequence length: After iterating through all the numbers, return the length of the longest sequence found.
Complexity
Time Complexity:
O(n), where n
is the number of elements in the array. Each element is inserted into the set and looked up a constant number of times.
Space Complexity:
O(n), where n
is the number of elements in the array. In the worst case, all elements are unique and stored in the set.
Code
C++
class Solution {
public:
int longestConsecutive(vector& nums) {
unordered_set numsSet(nums.begin(), nums.end());
int longestSequence = 0;
for (const int& num : nums) {
if (numsSet.find(num - 1) == numsSet.end()) {
int currentLength = 0;
while (numsSet.find(num + currentLength) != numsSet.end()) {
currentLength++;
}
longestSequence = max(longestSequence, currentLength);
}
}
return longestSequence;
}
};
Python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numsSet = set(nums)
longestSequence = 0
for num in nums:
if num - 1 not in numsSet:
currentLength = 1
while num + currentLength in numsSet:
currentLength += 1
longestSequence = max(longestSequence, currentLength)
return longestSequence
Java
class Solution {
public int longestConsecutive(int[] nums) {
Set numsSet = new HashSet<>();
for (int num : nums) {
numsSet.add(num);
}
int longestSequence = 0;
for (int num : nums) {
if (!numsSet.contains(num - 1)) {
int currentLength = 1;
while (numsSet.contains(num + currentLength)) {
currentLength++;
}
longestSequence = Math.max(longestSequence, currentLength);
}
}
return longestSequence;
}
}
JavaScript
var longestConsecutive = function (nums) {
const numsSet = new Set([...nums]);
let longestSequence = 0;
for (const num of nums) {
if (!numsSet.has(num - 1)) {
let currentLength = 0;
while (numsSet.has(num + currentLength)) {
currentLength++;
}
longestSequence = Math.max(longestSequence, currentLength)
}
}
return longestSequence;
};