This approach leverages a HashSet to store all unique elements of the input list. We then iterate through each number and check only when the number is the start of a sequence (i.e., one less than the number is not present in the set). If it is the start, we iterate to determine the length of the sequence by checking how long consecutive numbers exist in the set.
Time Complexity: O(n) because each number in the array is inserted into the set and looked up a constant number of times.
Space Complexity: O(n) for storing numbers in a set.
1def longestConsecutive(nums):
2 num_set = set(nums)
3 longest_streak = 0
4
5 for num in num_set:
6 if num - 1 not in num_set:
7 current_num = num
8 current_streak = 1
9
10 while current_num + 1 in num_set:
11 current_num += 1
12 current_streak += 1
13
14 longest_streak = max(longest_streak, current_streak)
15
16 return longest_streakThis method first converts the list to a set for O(1) lookups. It checks if the number is the start of a sequence (no preceding number exists) and counts how far the sequence goes, updating the maximum length found.
This approach involves sorting the array first and then performing a linear scan to find the longest sequence. Although not strictly O(n), this method shows how to approach the problem when constraints are slightly relaxed.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) with in-place sorting.
1#include <algorithm>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 int longestConsecutive(vector<int>& nums) {
8 if (nums.empty()) return 0;
9
10 sort(nums.begin(), nums.end());
11
12 int longestStreak = 1;
13 int currentStreak = 1;
14
15 for (int i = 1; i < nums.size(); ++i) {
16 if (nums[i] != nums[i-1]) {
17 if (nums[i] == nums[i-1] + 1) {
18 currentStreak += 1;
19 } else {
20 longestStreak = max(longestStreak, currentStreak);
21 currentStreak = 1;
22 }
23 }
24 }
25
26 return max(longestStreak, currentStreak);
27 }
28};This C++ code sorts the numbers first, then traverses them to count contiguous sequences, employing sorting to enable simpler sequence detection.