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] <= 109Problem Overview: Given an unsorted integer array, return the length of the longest sequence of consecutive numbers. The sequence elements do not need to appear next to each other in the array, but their values must form a continuous range like 1,2,3,4.
Approach 1: Using a HashSet and Iterative Checking (Time: O(n), Space: O(n))
This is the optimal strategy and relies on constant-time hash lookups. Insert every number from the array into a HashSet. Then iterate through each number and only start building a sequence if the previous number (num - 1) does not exist in the set. That condition identifies the start of a sequence. From there, repeatedly check if num + 1, num + 2, and so on exist in the set, counting the streak length. Each element is effectively processed once, giving O(n) time complexity with O(n) additional space.
This approach works because the set eliminates duplicates and enables O(1) membership checks. Instead of sorting or scanning repeatedly, you expand sequences only from valid starting points. Problems involving fast membership checks like this often rely on a hash table combined with traversal over an array.
Approach 2: Sorting and Linear Scan (Time: O(n log n), Space: O(1) or O(n) depending on sort)
Sorting simplifies the problem by placing numbers in ascending order. After sorting, iterate once through the array and track the current consecutive streak. If nums[i] == nums[i-1] + 1, extend the streak. If the values are equal, skip duplicates. Otherwise reset the streak counter and start a new sequence. Track the maximum length during the scan.
The main cost comes from sorting, which takes O(n log n) time. The scan itself is linear. This method is straightforward and easy to reason about, but it does not satisfy the strict O(n) requirement often mentioned in interviews. Still, it works well when modifying the array is allowed and implementation simplicity is preferred.
Recommended for interviews: Interviewers typically expect the HashSet O(n) approach. It demonstrates understanding of hash-based lookups and the ability to reduce redundant work by detecting sequence starting points. A sorting-based solution shows baseline problem-solving ability, but the optimal approach highlights stronger knowledge of hash table patterns and efficient traversal techniques sometimes discussed alongside structures like union find for grouping related elements.
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.
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.
Java
C++
JavaScript
C
C#
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.
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.
This C++ code sorts the numbers first, then traverses them to count contiguous sequences, employing sorting to enable simpler sequence detection.
JavaScript
Java
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) with in-place sorting.
| Approach | Complexity |
|---|---|
| Using a HashSet and Iterative Checking | 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. |
| Sorting and Linear Scan | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) with in-place sorting. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet with Iterative Sequence Expansion | O(n) | O(n) | Best general solution when O(n) performance is required |
| Sorting and Linear Scan | O(n log n) | O(1)–O(n) | Useful when modifying the array is acceptable and implementation simplicity matters |
Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE • NeetCode • 455,395 views views
Watch 9 more video solutions →Practice Longest Consecutive Sequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor