We can use a Hash Set. We add all elements to a set for O(1) lookups. Then, we iterate through the set. We only start building a sequence if the current number is the start of a sequence (i.e., num - 1 is not in the set). This avoids redundant work.
// Pseudocode: Sort the array and find the longest adjacent sequence.
// 1. Sort the array. Time: O(n log n).
// 2. Iterate and count max consecutive elements.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
sort(nums.begin(), nums.end());
int res = 1;
int curr = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i-1]) {
if (nums[i] == nums[i-1] + 1) {
curr++;
} else {
res = max(res, curr);
curr = 1;
}
}
}
return max(res, curr);
}
};// Pseudocode:
// 1. Convert nums to an unordered_set `num_set`.
// 2. Init max_len = 0.
// 3. For n in num_set:
// 4. If n - 1 not in num_set (it's the start of a sequence):
// 5. length = 1
// 6. while n + length in num_set:
// 7. length += 1
// 8. max_len = max(max_len, length)
// 9. Return max_len.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set(nums.begin(), nums.end());
int max_len = 0;
for (int n : num_set) {
if (num_set.find(n - 1) == num_set.end()) {
int length = 1;
while (num_set.find(n + length) != num_set.end()) {
length++;
}
max_len = max(max_len, length);
}
}
return max_len;
}
};Time: O(n). Although there is a nested while loop, it only runs for the start of a sequence, meaning each number is visited at most twice. Space: O(n) for the hash set.
- Empty array → returns 0.
- Array with duplicates → Set handles duplicates automatically.
This is a classic ‘Hash Set’ pattern. Identifying the START of a sequence is the core trick. If n-1 exists, skip n.