Longest Consecutive Sequence: A Set-Based Approach

The "Longest Consecutive Sequence" problem is an intriguing challenge that involves finding the length of the longest sequence of consecutive numbers in an unsorted array.

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. The sequence must be strictly consecutive, and the numbers in the sequence can appear in any order in the array.

Example

• Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore, its length is 4.

Set-Based Solution

Breaking Down the Solution

• Create a Set: Convert the array into a set to allow for O(1) lookups and to eliminate duplicates.
• Iterate Through the Set: For each number, check if it's the start of a sequence (i.e., num - 1 is not in the set).
• Expand the Sequence: If it's the start, count the length of the consecutive sequence by continuously checking the presence of the next numbers in the set.
• Track the Longest Sequence: Update the longest sequence length found so far.

Time Complexity

1. Creating the Set: Converting the array into a set has a time complexity of O(N), where N is the number of elements in the array. This is because each element is added to the set once.

2. Iterating Through the Set: The main loop iterates through each element of the set. For each element, it checks whether it is the start of a new sequence (i.e., whether num - 1 is not in the set).

3. Finding Consecutive Numbers: For each starting element of a sequence, the algorithm potentially iterates through the consecutive numbers following it. In the worst case, if there is a long consecutive sequence, this could seem like an additional nested loop. However, each element in the array is visited at most twice in these operations: once when it's checked as a potential start of a sequence, and once when it's counted as part of an existing sequence.

   The key insight is that, although there's a nested loop, each element from the original array contributes to the longest streak only once. This means the total number of operations is still proportional to N.

Putting it all together, the worst-case time complexity is O(N).

Space Complexity

The space complexity is primarily determined by the set used to store the elements of the array. Since the set contains every distinct element from the original array, the space complexity is O(N).

Summary

The set-based approach for the "Longest Consecutive Sequence" problem is efficient with a linear time complexity of O(N) and a linear space complexity of O(N), making it a suitable solution for large arrays.

Conclusion

The Longest Consecutive Sequence problem is an excellent application of sets in algorithms, demonstrating their utility in efficiently solving problems that involve uniqueness and ordering. It emphasizes the importance of choosing the right data structure for optimal performance in solving complex problems.

Rust Solution

Rust's HashSet<i32> is built in one expression by nums.into_iter().collect(), which consumes the Vec<i32> and discards duplicates for free — the type annotation on num_set is what tells collect which collection to produce. Iterating with for &num in &num_set borrows the set and destructures each element into an owned i32, so the loop body works with values rather than references. Because .contains takes its argument by reference, the lookups are spelled .contains(&(num - 1)) and .contains(&(current + 1)). The function returns usize and folds the running best with longest.max(streak) instead of a hand-written comparison.

Go Solution

Go has no built-in set type, so a map[int]bool stands in — created with make and populated by a for _, n := range nums loop that runs numSet[n] = true. The membership checks lean on Go's zero value: reading an absent key yields the map's default, so !numSet[num-1] and for numSet[current+1] work with a bare index and need no comma-ok v, ok := m[k] guard. Keys are walked with for num := range numSet, the counters advance with current++ / streak++, and the running best is updated by an explicit if streak > longest rather than a max helper.