Longest Consecutive Sequence
Java coding interview problem for Array Logic: Longest Consecutive Sequence.
The Longest Consecutive Sequence problem is one of the most important array problems in technical interviews.
It looks like a simple sorting problem, but the optimal solution requires understanding:
- HashSet
- Constant time lookup
- Sequence detection
- Avoiding unnecessary sorting
- Greedy traversal
This problem is commonly asked in interviews at:
- Amazon
- Microsoft
- Meta
- Netflix
What is Longest Consecutive Sequence?
Given an unsorted integer array, find the length of the longest sequence of consecutive numbers.
A consecutive sequence means:
Numbers increase by:
+1
continuously.
Example 1
Input:
nums = [100,4,200,1,3,2]
Sequences:
100
200
1,2,3,4
Longest sequence:
1,2,3,4
Length:
4
Output:
4
Example 2
Input:
nums = [0,3,7,2,5,8,4,6,0,1]
Longest sequence:
0,1,2,3,4,5,6,7,8
Length:
9
Output:
9
Example 3
Input:
nums = [10]
Output:
1
Understanding the Problem
Consider:
[9,1,4,7,3,-1,0,5,8,-1,6]
Numbers:
-1,0,1,3,4,5,6,7,8,9
Sequences:
Sequence 1:
-1,0,1
Length:
3
Sequence 2:
3,4,5,6,7,8,9
Length:
7
Answer:
7
Why Is This Question Asked in Interviews?
This problem tests:
1. Efficient Searching
Can you avoid:
O(n²)
searching?
2. Hashing Knowledge
Can you use:
HashSet
for O(1) lookup?
3. Algorithm Optimization
Can you improve:
O(n log n)
sorting solution to:
O(n)
?
4. Problem Pattern Recognition
Recognizing:
Sequence Detection
is important for many problems.
Real-World Applications
Log Processing
Finding longest continuous period of successful events.
Example:
Day IDs:
101,102,103,105
Longest sequence:
101,102,103
User Activity Analysis
Finding consecutive active days:
1,2,3,4,8
Longest streak:
1,2,3,4
Inventory Systems
Finding continuous product IDs.
Example:
1001,1002,1003,1005
Gaming Applications
Finding longest winning streak.
Example:
Win days:
1,2,3,5,6
Longest streak:
1,2,3
Problem Statement
Given an unsorted integer array:
nums
return the length of the longest consecutive elements sequence.
Constraints
Example:
0 <= nums.length <= 100000
Values:
-10^9 <= nums[i] <= 10^9
Requirements
The expected solution:
Time Complexity: O(n)
Understanding Sequence Logic
Input:
[100,4,200,1,3,2]
We need to identify:
Starting numbers.
A number is a sequence start when:
number - 1 does not exist
Example:
1
Check:
0 exists?
No.
Therefore:
1 is sequence start
Example:
2
Check:
1 exists?
Yes.
Therefore:
2 is not start
Array Visualization
Input:
[100,4,200,1,3,2]
HashSet:
{
100,
4,
200,
1,
3,
2
}
Start candidates:
100
200
1
Sequence from 1:
1 → 2 → 3 → 4
Length:
4
Dry Run
Input:
[100,4,200,1,3,2]
Create HashSet:
{
100,
4,
200,
1,
3,
2
}
Check:
100
Previous:
99
Does not exist.
Sequence:
100
Length:
1
Check:
4
Previous:
3
Exists.
Not a starting point.
Check:
200
Previous:
199
Does not exist.
Sequence:
200
Length:
1
Check:
1
Previous:
0
Does not exist.
Start sequence:
1
Continue:
1,2,3,4
Length:
4
Maximum:
4
Approach 1 — Brute Force Searching
The simplest solution:
For every number:
- Check if next number exists.
- Continue searching.
- Count sequence length.
Algorithm
For each element:
current = number
Check:
current + 1
until missing.
Example
Input:
[100,4,200,1,3,2]
For:
1
Search:
2
3
4
Length:
4
Java Program
public class LongestConsecutiveBruteForce {
public static int longestSequence(
int[] nums) {
int longest = 0;
for (int num : nums) {
int current = num;
int length = 1;
while (contains(nums,
current + 1)) {
current++;
length++;
}
longest =
Math.max(
longest,
length);
}
return longest;
}
private static boolean contains(
int[] nums,
int target) {
for (int num : nums) {
if (num == target) {
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] nums =
{100,4,200,1,3,2};
System.out.println(
longestSequence(nums));
}
}
Output
4
Step-by-Step Explanation
Input:
[100,4,200,1,3,2]
Start:
100
Check:
101
Not found.
Length:
1
Start:
1
Check:
2
Found.
Check:
3
Found.
Check:
4
Found.
Check:
5
Missing.
Length:
4
Answer:
4
Complexity Analysis
For each number:
Search array:
O(n)
Sequence length:
O(n)
Overall:
O(n²)
Space:
O(1)
Advantages
- Easy to understand.
- No extra data structure.
- Good for beginners.
Drawbacks
- Very slow.
- Repeated searching.
- Not suitable for large arrays.
Approach 2 — Sorting Approach
A common optimization:
- Sort the array.
- Scan consecutive values.
- Count streak length.
Example
Input:
[100,4,200,1,3,2]
After sorting:
[1,2,3,4,100,200]
Sequence:
1,2,3,4
Length:
4
Java Program
import java.util.Arrays;
public class LongestConsecutiveSorting {
public static int longestSequence(
int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int longest = 1;
int current = 1;
for (int i = 1;
i < nums.length;
i++) {
if (nums[i] ==
nums[i - 1] + 1) {
current++;
} else if (nums[i] !=
nums[i - 1]) {
current = 1;
}
longest =
Math.max(
longest,
current);
}
return longest;
}
}
Complexity Analysis
Sorting:
O(n log n)
Traversal:
O(n)
Overall:
O(n log n)
Space:
O(1)
Advantages
- Simple.
- Much faster than brute force.
- Easy to explain.
Drawbacks
- Modifies input array.
- Not optimal.
- Sorting is unnecessary.
Approach 3 — HashSet Approach (Optimal)
(Continued in Part 2)
We will achieve:
Time: O(n)
Space: O(n)
using:
HashSet
Approach 3 — HashSet Approach (Optimal)
The HashSet approach is the most efficient solution for the Longest Consecutive Sequence problem.
It achieves:
Time Complexity: O(n)
Space Complexity: O(n)
This is the preferred interview solution.
Core Idea
Instead of sorting the array, store all numbers in a HashSet.
HashSet provides:
O(1)
average lookup time.
Important Observation
A sequence starts only when:
number - 1
does not exist.
Example:
Array:
[100,4,200,1,3,2]
For:
2
Check:
1 exists?
Yes.
Therefore:
2 is not the start.
For:
1
Check:
0 exists?
No.
Therefore:
1 is the start.
Algorithm
- Add all numbers into HashSet.
- Traverse every number.
- Check if it is a sequence starting point:
num - 1 does not exist
- Count consecutive numbers:
num + 1
num + 2
num + 3...
- Update maximum length.
Java Program
import java.util.HashSet;
import java.util.Set;
public class LongestConsecutiveHashSet {
public static int longestSequence(
int[] nums) {
Set<Integer> set =
new HashSet<>();
for (int num : nums) {
set.add(num);
}
int longest = 0;
for (int num : nums) {
// Check starting point
if (!set.contains(num - 1)) {
int current = num;
int length = 1;
while (set.contains(
current + 1)) {
current++;
length++;
}
longest =
Math.max(
longest,
length);
}
}
return longest;
}
public static void main(String[] args) {
int[] nums =
{100,4,200,1,3,2};
System.out.println(
longestSequence(nums));
}
}
Output
4
Step-by-Step Explanation
Input:
[100,4,200,1,3,2]
Create HashSet:
{
100,
4,
200,
1,
3,
2
}
Check:
100
Previous:
99
Not found.
Start sequence:
100
Length:
1
Check:
4
Previous:
3
Exists.
Skip.
Check:
200
Previous:
199
Not found.
Sequence:
200
Length:
1
Check:
1
Previous:
0
Not found.
Start:
1
Continue:
1
2
3
4
Length:
4
Maximum:
4
Why Is This O(n)?
At first glance:
while(set.contains(current + 1))
looks like another loop.
But every number is processed only once as part of a sequence.
Example:
1 → 2 → 3 → 4
Numbers are not repeatedly counted from different starting points.
Therefore:
O(n)
Complexity Analysis
Creating HashSet:
O(n)
Searching:
O(n)
Total:
O(n)
Space:
O(n)
Advantages
- Optimal time complexity.
- No sorting required.
- Handles negative numbers.
- Handles duplicates.
- Interview preferred solution.
Drawbacks
- Requires extra memory.
- HashSet has memory overhead.
Handling Duplicate Values
Example:
Input:
[1,2,2,3,4,4]
HashSet:
{1,2,3,4}
Sequence:
1,2,3,4
Length:
4
Duplicates do not affect the answer.
Handling Negative Numbers
The algorithm works naturally with negative values.
Example:
Input:
[-3,-2,-1,0,5]
Sequences:
-3,-2,-1,0
Length:
4
Dry Run with Negative Numbers
Input:
[-2,-1,0,1,5]
HashSet:
{-2,-1,0,1,5}
Check:
-2
Previous:
-3
Not found.
Start:
-2
Sequence:
-2,-1,0,1
Length:
4
Answer:
4
Java Streams Approach
Java Streams can solve this problem, but they are not the best choice.
The algorithm requires:
- Fast lookup.
- Repeated membership checking.
HashSet is more suitable.
Streams Implementation
import java.util.Arrays;
public class LongestConsecutiveStreams {
public static int longestSequence(
int[] nums) {
return Arrays.stream(nums)
.distinct()
.sorted()
.reduce(
new int[]{0,0},
(result, value) -> {
if (result[0] == 0 ||
value ==
result[2-1]) {
result[0]++;
}
result[1] =
Math.max(
result[1],
result[0]);
return result;
},
(a,b) -> a);
}
}
In practice, the Stream solution becomes less readable.
The preferred Java approach:
HashSet
Comparison of All Approaches
| Approach | Time Complexity | Space Complexity | Recommendation |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Learning only |
| Sorting | O(n log n) | O(1) | Good alternative |
| HashSet | O(n) | O(n) | Best Interview Solution |
| Streams | O(n log n) | O(n) | Not Preferred |
Prefix Pattern vs HashSet Pattern
Many array problems use different patterns.
Prefix Pattern
Used when:
Need previous calculations.
Examples:
- Prefix Sum
- Product Except Self
HashSet Pattern
Used when:
Need fast existence checking.
Examples:
- Longest Consecutive Sequence
- Duplicate Detection
- Two Sum
Primitive vs Object Arrays
Primitive Array
Example:
int[]
Advantages:
- Faster.
- Less memory.
- Better performance.
Recommended for:
- Competitive programming.
- Large datasets.
Object Array
Example:
Integer[]
Advantages:
- Works with Collections.
- Supports generics.
Common Interview Mistakes
Mistake 1
Sorting immediately.
Example:
Arrays.sort(nums);
Although correct, it loses the O(n) solution opportunity.
Mistake 2
Checking every number as a sequence start.
Wrong:
Every number starts counting
Correct:
Only numbers without predecessors start counting
Mistake 3
Ignoring duplicates.
Example:
[1,2,2,3]
Should return:
3
Mistake 4
Using nested loops.
Complexity:
O(n²)
Edge Cases
| Input | Output |
|---|---|
[] |
0 |
[1] |
1 |
[1,2,3,4] |
4 |
[5,4,3,2,1] |
5 |
[1,1,2,3] |
3 |
[-3,-2,-1] |
3 |
Interview Follow-up Questions
Q1. Solve in O(n) time.
Q2. Solve without sorting.
Q3. Handle duplicate values.
Q4. Find the longest increasing consecutive sequence.
Q5. Return the actual sequence.
Q6. Solve using streaming data.
Q7. Find missing numbers from a sequence.
Related Problems
- Missing Number
- Contains Duplicate
- Two Sum
- Find Duplicate Number
- Longest Increasing Subsequence
- Range Compression
- Union of Arrays
Key Takeaways
The Longest Consecutive Sequence problem teaches an important optimization pattern:
Brute Force
↓
Sorting
↓
HashSet Lookup
The optimal interview solution:
HashSet Approach
Complexity:
Time: O(n)
Space: O(n)
The key idea:
A sequence only begins when there is no previous consecutive number.
Remember:
if (!set.contains(num - 1))
Start counting sequence
Frequently Asked Interview Questions
Q1. Why use HashSet?
Because it provides:
O(1)
average lookup.
Q2. Why check num - 1?
To identify sequence starting points.
Q3. Why is it O(n)?
Because each number is visited a limited number of times.
Q4. Can sorting solve this problem?
Yes.
Complexity:
O(n log n)
But HashSet is better.
Q5. How do you return the actual sequence?
Store:
start
end
while counting.
Interview Tip
When asked:
"Find longest consecutive sequence."
Explain the optimization journey:
- Brute Force → O(n²)
- Sorting → O(n log n)
- HashSet → O(n)
For senior-level interviews, focus on explaining:
Why only sequence starts are counted
That is the key insight behind the optimal solution.