Watch 10 video solutions for Longest Consecutive Sequence, a medium level problem involving Array, Hash Table, Union Find. This walkthrough by NeetCode has 455,395 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 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 | 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 |