LeetCode - Longest Consecutive Subsequence
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.
Problem statement taken from: https://leetcode.com/problems/longest-consecutive-sequence
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 <= 10^5
- -10^9 <= nums[i] <= 10^9
Explanation
Sorting
The naive solution is to sort the array and find the longest consecutive elements. After sorting the array, we remove the duplicate elements. We run a loop that counts the current number and maximum length of the consecutive elements. If the current number is not a consecutive element of the previous one, we reset the counter to 1 and update the maximum length.
A C++ snippet of the above approach is as below:
int ans = 0, count = 0;
sort(array, array + n);
vector<int> v;
v.push_back(array[0]);
for (int i = 1; i < n; i++) {
if (array[i] != array[i - 1])
v.push_back(array[i]);
}
for (int i = 0; i < v.size(); i++) {
if (i > 0 && v[i] == v[i - 1] + 1)
count++;
else
count = 1;
ans = max(ans, count);
}
return ans;The time complexity of the above approach is O(n(logn)) and space complexity is O(n).
HashMap
We can reduce the time complexity to O(n) by using a HashMap. Let's check the algorithm directly.
- set n = nums.size()
- if n == 0
return 0
- initialize map: map<int, int> m
- loop for i = 0; i < n; i++
- m[nums[i]]++
- set prev = m.begin()
maxLength = 1
result = 0
- loop for i = m.begin(); i < m.end(); i++
- if prev->first + 1 == i->first
- maxLength++
- else
- result = max(result, maxLength)
- maxLength = 1
- prev = i
- return max(result, maxLength)
The time complexity of the above approach is O(n), and the space complexity is O(n).
Let's check our algorithm in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
map<int, int> m;
for(int i = 0; i < n; i++) {
m[nums[i]];
}
auto prev = m.begin();
int maxLength = 1, result = 0;
for(auto i = m.begin(); i != m.end(); i++) {
if(prev->first + 1 == i->first) {
maxLength++;
} else {
result = max(result, maxLength);
maxLength = 1;
}
prev = i;
}
return max(result, maxLength);
}
};Golang solution
func max(a, b int) int {
if a > b {
return a
}
return b
}
func longestConsecutive(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
m := make(map[int]int)
for i := 0; i < n; i++ {
m[nums[i]]++
}
maxLength, result := 1, 0
for num := range m {
if _, ok := m[num-1]; !ok {
currNum := num
maxLength = 1
for {
if _, ok := m[currNum+1]; ok {
currNum += 1
maxLength += 1
} else {
break
}
}
result = max(result, maxLength)
}
}
return result
}Javascript solution
var longestConsecutive = function(nums) {
const n = nums.length;
if(n === 0) {
return 0
}
let set = new Set(nums)
let maxLength = 1, result = 0
for(let num of set) {
if(set.has(num - 1)) {
continue;
}
let current = num
maxLength = 1
while(set.has(current + 1)){
current++
maxLength++
}
result = Math.max(result, maxLength)
}
return result
};Dry Run
Let's dry-run our algorithm for Example 1.
Input: nums = [100, 4, 200, 1, 3, 2]
Step 1: int n = nums.size()
n = 6
Step 2: n == 0
6 == 0
false
Step 3: map<int, int> m
for(int i = 0; i < n; i++) {
m[nums[i]];
}
m = {
100: 0,
4: 0,
200: 0,
1: 0,
3: 0,
2: 0,
}
Step 4: prev = m.begin()
= 1
maxLength = 1
result = 0
Step 5: loop for i = m.begin(); i != m.end()
i = 1
1 != m.end()
true
if prev->first + 1 == i->first
1 + 1 == 1
2 == 1
false
else
result = max(result, maxLength)
= max(0, 1)
= 1
maxLength = 1
prev = i
= 1
i++
i -> 2
Step 6: loop for i != m.end()
i = 2
2 != m.end()
true
if prev->first + 1 == i->first
1 + 1 == 2
2 == 2
true
maxLength++
maxLength = 2
prev = i
= 2
i++
i -> 3
Step 7: loop for i != m.end()
i = 3
3 != m.end()
true
if prev->first + 1 == i->first
2 + 1 == 3
3 == 3
true
maxLength++
maxLength = 3
prev = i
= 3
i++
i -> 4
Step 8: loop for i != m.end()
i = 4
4 != m.end()
true
if prev->first + 1 == i->first
3 + 1 == 4
4 == 4
true
maxLength++
maxLength = 4
prev = i
= 4
i++
i -> 100
Step 9: loop for i != m.end()
i = 100
100 != m.end()
true
if prev->first + 1 == i->first
4 + 1 == 100
5 == 100
false
else
result = max(result, maxLength)
= max(1, 4)
= 4
maxLength = 1
prev = i
= 100
i++
i -> 200
Step 10: loop for i != m.end()
i = 200
200 != m.end()
true
if prev->first + 1 == i->first
100 + 1 == 200
101 == 200
false
else
result = max(result, maxLength)
= max(4, 4)
= 4
maxLength = 4
prev = i
= 200
i++
i -> end
Step 11: loop for i != m.end()
false
Step 12: return max(result, maxLength)
We return the answer as 4.