The Longest Consecutive Sequence problem is a fundamental challenge that tests your ability to identify patterns in unsorted data while maintaining efficiency. Whether you’re preparing for coding interviews or honing your problem-solving skills, understanding the problem statement is the first crucial step. Let’s break it down.
Understanding The Problem
The goal of this problem is to find the length of the longest consecutive sequence of numbers in an unsorted array of integers.
Key Requirements
• The sequence must consist of consecutive integers, but the numbers do not have to be adjacent in the array.
• The solution must run in O(n) time complexity for optimal performance.
Input and Output
Input
• An integer array nums[] (e.g., [100, 4, 200, 1, 3, 2]).
Output
• A single integer representing the length of the longest consecutive sequence in the array.
• Example:
• For the input [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so the output is 4.
Solving Longest Consecutive Sequence with a Naive Sorting Approach
A naive sorting approach is a great starting point for understanding the problem’s core mechanics. Let’s explore the sorting-based solution, its implementation, and its strengths and weaknesses.
Sorting is an intuitive way to solve the problem, as it aligns the numbers in increasing order, making consecutive sequences easy to identify. Once the array is sorted, the task reduces to counting the lengths of contiguous sequences.
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// Step 1: Sort the array
Arrays.sort(nums);
// Step 2: Initialize variables
int maxLen = 1; // Maximum sequence length
int currentLen = 1; // Current sequence length
// Step 3: Iterate through the sorted array
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
// Skip duplicates
continue;
}
if (nums[i] == nums[i - 1] + 1) {
// Consecutive element found
currentLen++;
} else {
// Sequence broken, update maxLen and reset currentLen
maxLen = Math.max(maxLen, currentLen);
currentLen = 1;
}
}
// Return the maximum of the last sequence and maxLen
return Math.max(maxLen, currentLen);
}1. Sort the Array:
• Sorting aligns the numbers in ascending order, making consecutive elements adjacent.
2. Iterate Through the Array:
• Compare each element with the previous one to determine if it’s part of a consecutive sequence.
• Skip duplicate values to avoid incorrect sequence lengths.
3. Track the Longest Sequence:
• Use variables to maintain the current sequence length and the maximum sequence length seen so far.
Solving Longest Consecutive Sequence with an Optimal HashSet Approach
While sorting provides a straightforward solution, it isn’t optimal for large datasets. A more efficient method leverages a HashSet, achieving O(n) time complexity.
A HashSet allows for O(1) average-time complexity for insertion and lookup operations. This property makes it ideal for problems that involve checking for the existence of elements, such as finding consecutive numbers in a sequence.
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0) return 0;
Set<Integer> uniqueNumbers = new HashSet<>();
for (int num : nums) {
uniqueNumbers.add(num);
}
int maxLengthOfSequence = 0;
for(int num : uniqueNumbers) {
if(!uniqueNumbers.contains(num - 1)) {
int currentLengthOfSequence = 1;
while(uniqueNumbers.contains(num + 1)) {
num++;
currentLengthOfSequence++;
}
maxLengthOfSequence = Math.max(maxLengthOfSequence, currentLengthOfSequence);
}
}
return maxLengthOfSequence;
}
}Step-By-Step Walkthrough
- Add Numbers to a HashSet
Set<Integer> uniqueNumbers = new HashSet<>();
for (int num : nums) {
uniqueNumbers.add(num);
}• This step ensures all unique numbers from the array are stored, eliminating duplicates.
• Duplicates are irrelevant for finding the longest consecutive sequence, as each unique number contributes only once to the calculation.
2. Create State to Track Max Sequence Length
int maxLengthOfSequence = 0;- Ensures the function returns the correct result by comparing and updating the maximum length as sequences are processed.
3. Loop Through Each Number
for(int num : uniqueNumbers) {
if(!uniqueNumbers.contains(num - 1)) {• Iterates through each number in the HashSet.
• Checks if the number is the start of a sequence by verifying that num – 1 does not exist in the HashSet.
4. Calculate the Length of the Sequence
int currentLengthOfSequence = 1;
while(uniqueNumbers.contains(num + 1)) {
num++;
currentLengthOfSequence++;
}• Initializes the length of the current sequence to 1 (the starting number itself).
• Increments the number (num++) and checks for the next consecutive number in the HashSet.
• Continues this process until the sequence breaks.
• Tracks the length of the current consecutive sequence starting from the smallest number.
• Stops when no more consecutive numbers are found.
6. Update the Maximum Sequence Length
maxLengthOfSequence = Math.max(maxLengthOfSequence, currentLengthOfSequence);- Compares the length of the current sequence with the maximum length seen so far and updates maxLengthOfSequence if the current sequence is longer.
Performance Analysis
1. Time Complexity: O(n)
• Adding numbers to the HashSet takes O(n).
• Iterating through the HashSet and processing sequences also takes O(n).
2. Space Complexity: O(n)
• The HashSet requires additional space proportional to the number of unique elements in the array.
Conclusion
This solution to the Longest Consecutive Sequence problem demonstrates the power of a HashSet for efficient lookups and sequence-building. By focusing only on sequence starting points and skipping redundant checks, the algorithm achieves optimal performance while maintaining simplicity. Mastering this approach equips you to tackle a wide range of array and sequence-based problems.
