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 elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109The key challenge in #128 Longest Consecutive Sequence is finding the length of the longest sequence of consecutive integers in an unsorted array while maintaining efficient time complexity. A naive approach that sorts the array works but increases the time complexity to O(n log n).
The optimal strategy uses a Hash Set. By inserting all numbers into a set, we can check whether a number is the start of a sequence (i.e., num - 1 is not present). If it is a starting point, we expand forward by checking num + 1, num + 2, and so on. This ensures each number is processed only once, leading to near O(n) time complexity.
Another conceptual approach uses Union-Find to group consecutive values as connected components. Each union operation links numbers differing by 1, and the largest component size represents the longest sequence. While less common in interviews, it helps illustrate connectivity-based reasoning.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set (Optimal) | O(n) | O(n) |
| Union Find | O(n α(n)) | O(n) |
| Sorting | O(n log n) | O(1) / O(n) |
NeetCode
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.
1def longestConsecutive(nums):
2 num_set = set(nums)
3 longest_streak = 0
4
5 for num in num_set:
6 if
This method first converts the list to a set for O(1) lookups. It checks if the number is the start of a sequence (no preceding number exists) and counts how far the sequence goes, updating the maximum length found.
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
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly asked in technical interviews at FAANG and other top tech companies. It tests understanding of hash-based optimization, set operations, and how to reduce time complexity from O(n log n) to O(n).
Yes, Union-Find can group numbers that differ by one into connected components. The size of the largest component represents the longest consecutive sequence. However, it is generally more complex than the hash set approach for this problem.
A hash set is the most effective data structure because it allows constant-time lookups to check if consecutive numbers exist. This makes it easy to detect the beginning of sequences and expand them efficiently.
The optimal approach uses a hash set to store all numbers and identify sequence starting points. From each valid start, you expand forward while consecutive numbers exist. This ensures each element is processed once, resulting in O(n) time complexity.
This Java code begins by sorting, relying on the sorted property to easily identify and count sequences in a straightforward linear scan.