Longest Consecutive Sequence
Problem Description
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:
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Example 3:
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
Solve it on LeetCode
Approaches
1. Sorting
Intuition:
The simplest way to find the longest consecutive sequence is to first sort the array. Once sorted, a consecutive sequence will appear as continuous numbers in the array. We can then iterate through the sorted array to count the lengths of consecutive sequences and return the length of the longest one.
- Sort the Array: Sorting the array costs O(n log n) time.
- Initialize counters: Use
currentStreakto keep track of the streak length, andlongestStreakto store the maximum length. - Iterate through the Array:
- Continue the streak if consecutive numbers are found.
- Reset
currentStreakif a gap is found. - Return the longest streak.
Code:
- Time Complexity: O(n log n), where n is the length of the array due to sorting.
- Space Complexity: O(1), apart from the input array storage.
2. HashSet and Intelligent Search
Intuition:
We can leverage a HashSet to eliminate duplicates and achieve O(n) complexity for finding consecutive sequences by only attempting to build from numbers that are not part of any smaller sequence.
- Add numbers to HashSet: This allows constant-time lookups.
- Iterate over the Set:
- For each number, check if it is the start of a sequence.
- Calculate the length of that sequence by incrementing and checking the presence of subsequent numbers.
- Track the maximum sequence length.
Code:
- Time Complexity: O(n), where n is the length of the array due to one pass through the elements and constant time lookups.
- Space Complexity: O(n), because of the space used by the HashSet.
3. Union-Find
Intuition:
We can use the union-find data structure to connect numbers that are part of consecutive sequences. Each element is a node, and paths connect consecutive numbers. Using path compression and union, we can efficiently find the size of the largest connected component, which corresponds to the longest sequence.
- Initialization: Treat each element in the array as its own set.
- Union by Rank: Connect consecutive numbers.
- Find the maximum component size.
Code:
- Time Complexity: Approximately O(n), taking into account the inverse Ackermann function in the union-find operations.
- Space Complexity: O(n), for the storage in the parent and rank maps.