Longest Consecutive Sequence(LeetCode)
Problem Statement
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Examples
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints
0 <= nums.length <= 105-109 <= nums[i] <= 109
Solution
We can solve the problem of finding the longest consecutive sequence in an array using four different approaches: Brute Force, Sorting, Hash Table with an unordered map, and Hash Table with an unordered set. Each approach has its own advantages and drawbacks in terms of time and space complexity.
Approach 1: Brute Force
Algorithm
- Initialize a variable to keep track of the longest consecutive sequence.
- Iterate through each element in the array.
- For each element, use a nested loop to check if the next consecutive number exists in the array.
- Keep track of the length of the current consecutive sequence.
- Update the longest consecutive sequence if the current sequence is longer.
- Return the length of the longest consecutive sequence.
Implementation
class Solution {
private:
bool longestConsecutive(vector<int>& nums, int target){
int n = nums.size();
for(int i=0; i<n; i++){
if(nums[i] == target){
return true;
}
}
return false;
}
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
int longestConsecutiveSequence = 0;
for(auto num : nums){
int currentNumber = num;
int currentConsecutiveSequence = 1;
while(longestConsecutive(nums, currentNumber+1)){
currentNumber += 1;
currentConsecutiveSequence += 1;
}
longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);
}
return longestConsecutiveSequence;
}
};
Complexity Analysis
- Time complexity: O(N^3)
- Space complexity: O(1)
Approach 2: Sorting
Algorithm
- Sort the array.
- Initialize variables to keep track of the current consecutive sequence and the longest consecutive sequence.
- Iterate through the sorted array.
- If the current element is consecutive to the previous element, increase the current sequence length.
- If not, update the longest sequence length and reset the current sequence length.
- Return the length of the longest consecutive sequence.
Implementation
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
if(n == 0){
return 0;
}
sort(nums.begin(), nums.end());
int currentConsecutiveSequence = 1;
int longestConsecutiveSequence = 0;
for(int i=1; i<n; i++){
if(nums[i] != nums[i-1]){
if(nums[i] == nums[i-1] + 1){
currentConsecutiveSequence++;
}
else{
longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);
currentConsecutiveSequence = 1;
}
}
}
return max(longestConsecutiveSequence, currentConsecutiveSequence);
}
};
Complexity Analysis
- Time complexity: O(N log N)
- Space complexity: O(1)
Approach 3: Hash Table with Unordered Map
Algorithm
- Create an unordered map to store each element in the array.
- Iterate through the array and mark each element as the start of a sequence if it is not part of a longer sequence.
- For each element, count the length of the sequence it starts and update the maximum length.
- Return the length of the longest consecutive sequence.
Implementation
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, bool> map;
for(int i = 0; i<nums.size(); i++){
map[nums[i]] = true;
}
for(int i=0; i<nums.size(); i++){
if(map.count(nums[i]-1) > 0){
map[nums[i]] = false;
}
}
int maxlen = 0;
for(int i=0; i<nums.size(); i++){
if(map[nums[i]] == true){
int j=0; int count=0;
while(map.count(nums[i]+j) > 0){
j++;
count++;
}
if(count>maxlen){
maxlen = count;
}
}
}
return maxlen;
}
};
Complexity Analysis
- Time complexity: O(N)
- Space complexity: O(N)
Approach 4: Hash Table with Unordered Set
Algorithm
- Create an unordered set to store each element in the array.
- Iterate through the array.
- For each element, check if it is the start of a sequence.
- If it is, count the length of the sequence it starts and update the maximum length.
- Return the length of the longest consecutive sequence.
Implementation
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set;
for(int num : nums){
set.insert(num);
}
int longestConsecutiveSequence = 0;
for(int num : nums){
if(set.find(num-1) == set.end()){
int currentNumber = num;
int currentConsecutiveSequence = 1;
while(set.find(currentNumber+1) != set.end()){
currentNumber++;
currentConsecutiveSequence++;
}
longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);
}
}
return longestConsecutiveSequence;
}
};
Complexity Analysis
- Time complexity: O(N)
- Space complexity: O(N)
Conclusion
Among the four approaches, the optimized approaches using hash tables (unordered map or unordered set) are the most efficient with a time complexity of O(N) and space complexity of O(N). The brute force approach, while straightforward, is inefficient with a time complexity of O(N^3). The sorting approach is better but still not as efficient as the hash table approaches. The hash table with unordered set approach is particularly simple and effective for solving the longest consecutive sequence problem in linear time.