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.
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.