Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Constraints:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^9
Examples:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4].
Input: [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8].
Solutions
Hash Set
We use a hash set to store the numbers in the array. Then we iterate over the set and for each number, we check if it is the start of a sequence (i.e., `num - 1` is not in the set). If it is, we then check for the presence of `num + 1`, `num + 2`, etc. in the set and keep track of the length of the current sequence. We update the longest streak if the current sequence is longer.
class Solution {
public: int longestConsecutive(vector<int>& nums) {
unordered_set<int> numSet(nums.begin(), nums.end());
int longestStreak = 0;
for (int num : numSet) {
if (numSet.find(num - 1) == numSet.end()) {
int currentNum = num;
int currentStreak = 1;
while (numSet.find(currentNum + 1) != numSet.end()) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
;Follow-up:
What if the input array is very large and we want to find the longest consecutive sequence in a streaming fashion?
