Dare2Solve
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.
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.
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.
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.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> 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;
}
};
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
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> 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;
}
}
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;
};