128. Longest Consecutive Sequence - Detailed Explanation
Problem Statement
You are given an unsorted array of integers nums. Your task is to find the length of the longest consecutive elements sequence.
Example 1:
Input:
nums = [100, 4, 200, 1, 3, 2]
Output:
4
Explanation: The longest consecutive sequence is [1, 2, 3, 4], which has a length of 4.
Example 2:
Input:
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output:
9
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has a length of 9.
Constraints:
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9- The solution must run in O(N) time complexity.
Hints to Solve the Problem
- Brute Force Approach: Try to check each element and see how long its consecutive sequence is.
- Sorting Approach: Sorting the array and checking for consecutive elements works but is not optimal for time complexity.
- Optimized Approach: Using a HashSet can help determine the start of a sequence efficiently by checking if
num-1exists.
Approach 1: Brute Force (Try Every Possible Sequence)
Explanation:
- Iterate over each number in
nums. - For each number, start a sequence from that number and keep checking for the next consecutive number (
num + 1). - Count how long the consecutive sequence continues.
- Update the maximum length found.
This approach tries every possible starting point and checks consecutively until the sequence breaks.
Python Code:
Complexity Analysis:
- Time Complexity: O(N²) in the worst case. Checking for
current_num + 1 in numsis an O(N) operation, repeated for N numbers. - Space Complexity: O(1), as no extra data structures are used.
Java Code (Brute Force Approach)
In this brute force Java solution, we manually check for the next number in the sequence using a helper function contains. This is highly inefficient for large arrays due to the nested loop (contains itself loops through the array).
Approach 2: Optimized Solution (Using HashSet)
Explanation:
-
Use a HashSet to store all numbers for quick lookups (O(1) average time for
inoperations). -
Iterate through each number in the set.
-
For each number, first check if it could be the start of a sequence by ensuring
num - 1is not in the set. This step ensures we only count each sequence once (starting at its smallest element). -
If
numis a start of a sequence, then iterate forward (num + 1, num + 2, ...) counting consecutive numbers until the sequence breaks. -
Keep track of the longest sequence length found.
By only starting counts at the beginning of sequences, we avoid unnecessary work and achieve linear time complexity.
Python Code:
Complexity Analysis:
- Time Complexity: O(N) since each number is processed only once.
- Space Complexity: O(N) for storing the HashSet.
Summary:
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(N²) | O(1) | Too slow for large inputs |
| Optimized HashSet | O(N) | O(N) | Efficient solution |
Java Code (Optimized Solution with HashSet)
In this optimized Java solution, a HashSet is used to allow O(1) containment checks. We only initiate a sequence count when we find a number that has no predecessor in the set (i.e., num-1 is not in the set), then count how long the sequence goes on.
Edge Cases
- Empty List:
nums = []→ Output:0(no elements, so no sequence). - Single Element List:
nums = [7]→ Output:1(only one number, sequence length is 1). - All Unique Non-Consecutive Elements:
nums = [10, 20, 30, 40]→ Output:1(no two numbers form a consecutive sequence, so the longest is any single number by itself). - Large List with Random Order: The algorithm should still run efficiently in O(N) time even for large inputs (tens of thousands of elements or more, in arbitrary order).
Common Mistakes
- Using sorting to solve the problem. Sorting takes O(N log N) time, which is acceptable in many cases but not optimal if an O(N) solution exists. Moreover, after sorting, you'd still need to scan through to count consecutive sequences.
- Forgetting to check for the start of a sequence. If you don't ensure
num-1is not present, you might count the same sequence multiple times or do unnecessary work. - Not handling the case of an empty array. Make sure to return 0 when
numshas no elements.
Related Problems for Practice
- Longest Increasing Subsequence – Similar idea of finding a sequence, but it doesn't require the numbers to be consecutive in value (just increasing) and typically is solved with dynamic programming.
- Find All Numbers Disappeared in an Array – Also uses the idea of presence/absence in an array of a certain range of numbers, can be solved using sets or in-place marking.
- Subarray Sum Equals K – Different problem (sums in subarrays) but also can be approached with a HashSet/HashMap for optimized lookups, illustrating the power of hashing in array problems.
GET YOUR FREE
Coding Questions Catalog
