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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LongestConsecutive(int[] nums) {
6 HashSet<int> numSet = new HashSet<int>(nums);
7 int longestStreak = 0;
8
9 foreach (int num in numSet) {
10 if (!numSet.Contains(num - 1)) {
11 int currentNum = num;
12 int currentStreak = 1;
13
14 while (numSet.Contains(currentNum + 1)) {
15 currentNum++;
16 currentStreak++;
17 }
18
19 longestStreak = Math.Max(longestStreak, currentStreak);
20 }
21 }
22
23 return longestStreak;
24 }
25}The C# solution creates a HashSet for unique elements and straightforward sequence detection by skipping non-starter elements, counting sequences where they start.
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.