Approach

Longest Consecutive Sequence

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Approach: HashSet (Optimal - O(n))

Intuition

The key insight is to use a HashSet to enable O(1) lookups. For each number, if it's the start of a sequence (i.e., num-1 is not in the set), we can count how long the sequence extends.

Key Steps

Add all numbers to a set for O(1) lookup
Find sequence starts: Only start counting from numbers where num-1 doesn't exist
Count sequence length: Keep checking num+1, num+2, etc.
Track maximum length seen

Why This Works

By only starting sequences from their beginning (when num-1 doesn't exist), each number is visited at most twice
Time complexity: O(n) despite nested loop (amortized)
Space complexity: O(n) for the set

Algorithm

def longestConsecutive(nums):
    num_set = set(nums)
    max_length = 0
    
    for num in num_set:
        # Only start sequence from the beginning
        if num - 1 not in num_set:
            current = num
            length = 1
            
            # Count consecutive numbers
            while current + 1 in num_set:
                current += 1
                length += 1
            
            max_length = max(max_length, length)
    
    return max_length

Time Complexity

O(n): Each number is visited at most twice (once in outer loop, once in inner)

Space Complexity

O(n): HashSet storage

Alternative Approaches

1. Sorting - O(n log n)

Sort the array and count consecutive sequences. Simple but doesn't meet O(n) requirement.

2. Union-Find - O(n α(n))

Use union-find to group consecutive numbers. More complex but also achieves near-linear time.

Solution

java

1/**
2 * Longest Consecutive Sequence
3 * Time: O(n) with HashSet, O(n log n) with sorting
4 * Space: O(n)
5 */
6
7import java.util.*;
8
9// Approach 1: HashSet (Optimal - O(n))
10class Solution {
11    public int longestConsecutive(int[] nums) {
12        if (nums.length == 0) return 0;
13        
14        Set<Integer> numSet = new HashSet<>();
15        for (int num : nums) {
16            numSet.add(num);
17        }
18        
19        int maxLength = 0;
20        
21        for (int num : numSet) {
22            // Only start counting from sequence start
23            if (!numSet.contains(num - 1)) {
24                int current = num;
25                int length = 1;
26                
27                // Count consecutive numbers
28                while (numSet.contains(current + 1)) {
29                    current++;
30                    length++;
31                }
32                
33                maxLength = Math.max(maxLength, length);
34            }
35        }
36        
37        return maxLength;
38    }
39}
40
41// Approach 2: Sorting - O(n log n)
42class Solution2 {
43    public int longestConsecutive(int[] nums) {
44        if (nums.length == 0) return 0;
45        
46        Arrays.sort(nums);
47        int maxLength = 1;
48        int currentLength = 1;
49        
50        for (int i = 1; i < nums.length; i++) {
51            if (nums[i] == nums[i-1]) {
52                // Skip duplicates
53                continue;
54            } else if (nums[i] == nums[i-1] + 1) {
55                // Consecutive
56                currentLength++;
57                maxLength = Math.max(maxLength, currentLength);
58            } else {
59                // Break in sequence
60                currentLength = 1;
61            }
62        }
63        
64        return maxLength;
65    }
66}
67
68// Approach 3: HashMap with sequence merging
69class Solution3 {
70    public int longestConsecutive(int[] nums) {
71        if (nums.length == 0) return 0;
72        
73        Map<Integer, Integer> numMap = new HashMap<>();
74        int maxLength = 0;
75        
76        for (int num : nums) {
77            if (numMap.containsKey(num)) continue;
78            
79            int left = numMap.getOrDefault(num - 1, 0);
80            int right = numMap.getOrDefault(num + 1, 0);
81            
82            int length = left + right + 1;
83            maxLength = Math.max(maxLength, length);
84            
85            // Update boundaries
86            numMap.put(num, length);
87            numMap.put(num - left, length);
88            numMap.put(num + right, length);
89        }
90        
91        return maxLength;
92    }
93}
94