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.
1#include <unordered_set>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 int longestConsecutive(vector<int>& nums) {
8 unordered_set<int> numSet(nums.begin(), nums.end());
9 int longestStreak = 0;
10
11 for (const int &num : numSet) {
12 if (!numSet.count(num - 1)) {
13 int currentNum = num;
14 int currentStreak = 1;
15
16 while (numSet.count(currentNum + 1)) {
17 currentNum += 1;
18 currentStreak += 1;
19 }
20
21 longestStreak = max(longestStreak, currentStreak);
22 }
23 }
24
25 return longestStreak;
26 }
27};The C++ solution efficiently uses an unordered_set to gather unique numbers and check sequence start points. Subsequent numbers are checked to determine streak length.
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.
1import java.util.Arrays;
2
3class Solution {
4 public int longestConsecutive(int[] nums) {
5 if (nums.length == 0) {
6 return 0;
7 }
8
9 Arrays.sort(nums);
10
11 int longestStreak = 1;
12 int currentStreak = 1;
13
14 for (int i = 1; i < nums.length; i++) {
15 if (nums[i] != nums[i - 1]) {
16 if (nums[i] == nums[i - 1] + 1) {
17 currentStreak++;
18 } else {
19 longestStreak = Math.max(longestStreak, currentStreak);
20 currentStreak = 1;
21 }
22 }
23 }
24
25 return Math.max(longestStreak, currentStreak);
26 }
27}This Java code begins by sorting, relying on the sorted property to easily identify and count sequences in a straightforward linear scan.