Longest Consecutive Sequence - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem Overview: Given an unsorted integer array, return the length of the longest sequence of consecutive numbers. The sequence elements do not need to appear in order in the array, but they must form continuous values such as 1,2,3,4.
Approach 1: Using a HashSet and Iterative Checking (O(n) time, O(n) space)
The optimal strategy uses a hash table to store every number for constant-time lookups. Insert all values into a HashSet, then iterate through the set and treat a number as the start of a sequence only if num - 1 is not present. From that starting point, repeatedly check if num + 1, num + 2, and so on exist in the set, counting the sequence length. Each number is visited at most once as part of a sequence expansion, giving O(n) time and O(n) space. This approach avoids sorting and relies on constant-time membership checks provided by hash tables. It works well for large unsorted inputs where linear performance matters.
Approach 2: Sorting and Linear Scan (O(n log n) time, O(1) extra space)
A simpler alternative sorts the array first, which groups consecutive numbers together. After sorting, perform a single pass and track the current streak length whenever the difference between adjacent elements is exactly 1. If the numbers are equal, skip duplicates to avoid resetting the streak. When the gap becomes larger than 1, reset the counter and continue scanning. Sorting costs O(n log n) time while the scan is O(n), and the space complexity is O(1) if the sort is done in place. This approach uses basic array operations and is easy to implement, though it does not meet the linear-time constraint typically expected in interviews.
Recommended for interviews: Interviewers usually expect the HashSet O(n) solution. It shows you recognize that sequence starts can be detected using num - 1 checks and that constant-time lookups eliminate the need for sorting. Explaining the sorting approach first demonstrates baseline reasoning, while implementing the hash-based solution shows stronger algorithmic thinking with hash tables and efficient iteration.
Approach 1: Using a HashSet and Iterative Checking
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.
Complexity
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.
Approach 2: Sorting and Linear Scan
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.
Code
C++
JavaScript
Java
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) with in-place sorting.
Approach 3: Hash Table
We can use a hash table s to store all the elements in the array, a variable ans to record the length of the longest consecutive sequence, and a hash table d to record the length of the consecutive sequence each element x belongs to.
Next, we iterate through each element x in the array, using a temporary variable y to record the maximum value of the current consecutive sequence, initially y = x. Then, we continuously try to match y+1, y+2, y+3, \dots until we can no longer match. During this process, we remove the matched elements from the hash table s. The length of the consecutive sequence that the current element x belongs to is d[x] = d[y] + y - x, and then we update the answer ans = max(ans, d[x]).
After the iteration, we return the answer ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: Hash Table (Optimization)
Similar to Solution 1, we use a hash table s to store all the elements in the array and a variable ans to record the length of the longest consecutive sequence. However, we no longer use a hash table d to record the length of the consecutive sequence each element x belongs to. During the iteration, we skip elements where x-1 is also in the hash table s. If x-1 is in the hash table s, then x is definitely not the start of a consecutive sequence, so we can directly skip x.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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. |
| Hash Table | — |
| Hash Table (Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet + Sequence Expansion | O(n) | O(n) | General case and interview-preferred solution for unsorted arrays |
| Sorting + Linear Scan | O(n log n) | O(1) | Useful when sorting is acceptable or memory must stay minimal |
Video Solution
Longest Consecutive Sequence | Google Interview Question | Brute Better Optimal • take U forward • 669,850 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Consecutive Sequence easy or hard?
How to solve Longest Consecutive Sequence in O(n)?
Longest Consecutive Sequence Python or Java solution?
What is the best approach for Longest Consecutive Sequence?
What data structure is used in Longest Consecutive Sequence?
What is the time complexity of Longest Consecutive Sequence?
Is Longest Consecutive Sequence asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Longest Consecutive Sequence with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor