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.
1function longestConsecutive(nums) {
2 const numSet = new Set(nums);
3 let longestStreak = 0;
4
5 for (let num of numSet) {
6 if (!numSet.has(num - 1)) {
7 let currentNum = num;
8 let currentStreak = 1;
9
10 while (numSet.has(currentNum + 1)) {
11 currentNum += 1;
12 currentStreak += 1;
13 }
14
15 longestStreak = Math.max(longestStreak, currentStreak);
16 }
17 }
18
19 return longestStreak;
20}The JavaScript function uses a Set to ensure uniqueness and direct access. It determines sequence start points and calculates the longest sequence length iteratively.
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.
1function longestConsecutive(nums) {
2 if (nums.length === 0) return 0;
3
4 nums.sort((a, b) => a - b);
5
6 let longestStreak = 1;
7 let currentStreak = 1;
8
9 for (let i = 1; i < nums.length; i++) {
10 if (nums[i] !== nums[i - 1]) {
11 if (nums[i] === nums[i - 1] + 1) {
12 currentStreak += 1;
13 } else {
14 longestStreak = Math.max(longestStreak, currentStreak);
15 currentStreak = 1;
16 }
17 }
18 }
19
20 return Math.max(longestStreak, currentStreak);
21}By sorting the array, this JavaScript solution ensures that consecutive sequences are adjacent, simplifying the counting logic thereafter.