12. Longest Consecutive Sequence
🔗 LeetCode Problem: 128. Longest Consecutive Sequence
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Union Find
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 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
Explanation: The longest consecutive sequence is [0,1,2,3,4,5,6,7,8].
Constraints:
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
🎨 Visual Understanding
The Problem Visualized
Input: [100, 4, 200, 1, 3, 2]
Unsorted array:
[100, 4, 200, 1, 3, 2]
If we sort them:
[1, 2, 3, 4, 100, 200]
└─consecutive─┘
Consecutive sequences:
- [1, 2, 3, 4] → length 4 ✓ (longest)
- [100] → length 1
- [200] → length 1
Result: 4
What is a Consecutive Sequence?
Consecutive = Numbers differ by exactly 1
Examples:
[1, 2, 3, 4] ✓ Consecutive (1→2→3→4)
[1, 3, 5, 7] ✗ Not consecutive (gaps of 2)
[5, 4, 3, 2] ✓ Can be reordered: [2, 3, 4, 5]
[1, 2, 2, 3] ✓ Duplicates ignored: [1, 2, 3]
Key insight: Order in array doesn't matter!
We just need to find which numbers form sequences.
Approach Comparison
Approach 1: Sorting
[100, 4, 200, 1, 3, 2]
↓ Sort
[1, 2, 3, 4, 100, 200]
Then scan for consecutive runs
Time: O(n log n) - sorting
✗ Violates O(n) requirement
Approach 2: HashSet (Optimal)
Convert to set: {100, 4, 200, 1, 3, 2}
For each number, check if it's a sequence start:
- If (num-1) NOT in set → this is a start!
- Count how far sequence goes: num+1, num+2, ...
1: is 0 in set? No → START! Count: 1,2,3,4 → length 4
2: is 1 in set? Yes → NOT a start (skip)
3: is 2 in set? Yes → NOT a start (skip)
4: is 3 in set? Yes → NOT a start (skip)
100: is 99 in set? No → START! Count: 100 → length 1
200: is 199 in set? No → START! Count: 200 → length 1
Max length: 4 ✓
Time: O(n) - each number visited at most twice
🎯 Approach 1: Sorting
The Most Natural Thinking 💭
Core Logic:
Sort the array, then scan for consecutive sequences:
1. Sort array
2. Scan from left to right
3. Track current sequence length
4. If current number = previous number + 1 → extend sequence
5. If current number = previous number → skip duplicate
6. Otherwise → start new sequence
7. Keep track of maximum length
Why This Works: - Sorting brings consecutive numbers together - Easy to identify sequences with single scan - Simple to implement
Why This Fails Requirements: - Sorting is O(n log n) - Problem requires O(n) time - Good for understanding, not for submission
Implementation
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// Sort the array
Arrays.sort(nums);
int maxLength = 1;
int currentLength = 1;
for (int i = 1; i < nums.length; i++) {
// Skip duplicates
if (nums[i] == nums[i - 1]) {
continue;
}
// Check if consecutive
if (nums[i] == nums[i - 1] + 1) {
currentLength++;
} else {
// Start new sequence
maxLength = Math.max(maxLength, currentLength);
currentLength = 1;
}
}
return Math.max(maxLength, currentLength);
}
Step-by-Step Execution: nums = [100,4,200,1,3,2]
Step 1: Sort array
[100, 4, 200, 1, 3, 2] → [1, 2, 3, 4, 100, 200]
Step 2: Scan for sequences
═══════════════════════════════════════════════════════════════════
i=0: nums[0]=1
currentLength = 1
maxLength = 1
i=1: nums[1]=2
Compare with nums[0]=1
2 == 1+1 ✓ Consecutive
currentLength = 2
i=2: nums[2]=3
Compare with nums[1]=2
3 == 2+1 ✓ Consecutive
currentLength = 3
i=3: nums[3]=4
Compare with nums[2]=3
4 == 3+1 ✓ Consecutive
currentLength = 4
maxLength = 4
i=4: nums[4]=100
Compare with nums[3]=4
100 != 4+1 ✗ Not consecutive
Update maxLength = max(4, 4) = 4
Reset currentLength = 1
i=5: nums[5]=200
Compare with nums[4]=100
200 != 100+1 ✗ Not consecutive
Update maxLength = max(4, 1) = 4
Reset currentLength = 1
Final check: max(4, 1) = 4
Result: 4
⏰ Time: O(n log n) - sorting dominates
💾 Space: O(1) or O(n) depending on sort algorithm
✅ Approach 2: HashSet (Optimal)
The Breakthrough Insight 💡
Core Logic:
Key Observation:
We only need to start counting from the BEGINNING of sequences!
How to identify sequence start?
- A number is a sequence start if (num-1) is NOT in the array
Strategy:
1. Put all numbers in HashSet (O(n))
2. For each number:
- Check if num-1 exists in set
- If NO → this is a sequence start!
- Count consecutive numbers: num+1, num+2, num+3...
- Track maximum length
3. If YES → skip (we'll count from the start later)
Why this is O(n):
- Building set: O(n)
- Each number visited as potential start: O(n)
- Each number counted in sequence at most once
- Total: O(n)
Visual Explanation:
nums = [1, 2, 3, 4, 100, 200]
set = {1, 2, 3, 4, 100, 200}
Check 1: Is 0 in set? No → START!
Count: 1→2→3→4 (all in set)
Length: 4
Check 2: Is 1 in set? Yes → Skip (not a start)
Check 3: Is 2 in set? Yes → Skip
Check 4: Is 3 in set? Yes → Skip
Check 100: Is 99 in set? No → START!
Count: 100 (101 not in set)
Length: 1
Check 200: Is 199 in set? No → START!
Count: 200 (201 not in set)
Length: 1
Max: 4
Why This is Better: - O(n) time complexity (meets requirement!) - Each number checked at most twice - No sorting needed - O(n) space for HashSet (acceptable trade-off)
Implementation
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// Put all numbers in HashSet for O(1) lookup
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLength = 0;
// Check each number as potential sequence start
for (int num : set) {
// Only start counting if this is the beginning of a sequence
if (!set.contains(num - 1)) {
int currentNum = num;
int currentLength = 1;
// Count how long the sequence goes
while (set.contains(currentNum + 1)) {
currentNum++;
currentLength++;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}
Step-by-Step Execution: nums = [100,4,200,1,3,2]
Step 1: Build HashSet
═══════════════════════════════════════════════════════════════════
Add 100 → set = {100}
Add 4 → set = {100, 4}
Add 200 → set = {100, 4, 200}
Add 1 → set = {100, 4, 200, 1}
Add 3 → set = {100, 4, 200, 1, 3}
Add 2 → set = {100, 4, 200, 1, 3, 2}
Final set: {100, 4, 200, 1, 3, 2}
Step 2: Find longest sequence
═══════════════════════════════════════════════════════════════════
Check num=100:
├─ Is 99 in set? No → This is a sequence START!
├─ currentNum = 100, currentLength = 1
├─ Is 101 in set? No
├─ Sequence: [100]
└─ maxLength = max(0, 1) = 1
Check num=4:
├─ Is 3 in set? Yes → NOT a start, skip
└─ (Will be counted when we process 1)
Check num=200:
├─ Is 199 in set? No → This is a sequence START!
├─ currentNum = 200, currentLength = 1
├─ Is 201 in set? No
├─ Sequence: [200]
└─ maxLength = max(1, 1) = 1
Check num=1:
├─ Is 0 in set? No → This is a sequence START!
├─ currentNum = 1, currentLength = 1
├─ Is 2 in set? Yes → currentNum=2, currentLength=2
├─ Is 3 in set? Yes → currentNum=3, currentLength=3
├─ Is 4 in set? Yes → currentNum=4, currentLength=4
├─ Is 5 in set? No → Stop
├─ Sequence: [1, 2, 3, 4]
└─ maxLength = max(1, 4) = 4
Check num=3:
├─ Is 2 in set? Yes → NOT a start, skip
└─ (Already counted in sequence starting at 1)
Check num=2:
├─ Is 1 in set? Yes → NOT a start, skip
└─ (Already counted in sequence starting at 1)
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 4
═══════════════════════════════════════════════════════════════════
Another Example: nums = [0,3,7,2,5,8,4,6,0,1]
Build set: {0, 3, 7, 2, 5, 8, 4, 6, 1}
(Duplicate 0 handled automatically)
Check num=0:
Is -1 in set? No → START!
Count: 0→1→2→3→4→5→6→7→8
Length: 9 ✓
Check num=3:
Is 2 in set? Yes → Skip
Check num=7:
Is 6 in set? Yes → Skip
(All other numbers have predecessor in set, so skipped)
Result: 9
⏰ Time: O(n) - each number visited at most twice
💾 Space: O(n) - HashSet storage
🔍 Edge Cases
Case 1: Empty array
Input: []
Output: 0
Strategy: Handle at beginning
Case 2: Single element
Input: [1]
Output: 1
Case 3: All consecutive
Input: [1,2,3,4,5]
Output: 5
Case 4: No consecutive (all isolated)
Input: [1,3,5,7,9]
Output: 1
Strategy: Each number is its own sequence
Case 5: Duplicates
Input: [1,2,2,3]
Output: 3
Strategy: HashSet automatically handles duplicates
Case 6: Negative numbers
Input: [-1,0,1,2]
Output: 4
Strategy: Algorithm works with any integers
Case 7: Large gaps
Input: [1,2,3,100,101,102]
Output: 3
Strategy: Two separate sequences
Case 8: Descending order
Input: [5,4,3,2,1]
Output: 5
Strategy: Order doesn't matter, still forms sequence
Case 9: Single very long sequence
Input: [1,2,3,...,100000]
Output: 100000
Strategy: O(n) handles efficiently
Common Mistakes
Mistake 1: Counting each number separately
❌ Wrong: Start count from every number
✓ Right: Only start from sequence beginning (num-1 not in set)
Mistake 2: Not handling duplicates
❌ Wrong: Count duplicates as extending sequence
✓ Right: HashSet automatically removes duplicates
Mistake 3: Using sorting and claiming O(n)
❌ Wrong: Sort then scan - this is O(n log n)
✓ Right: Use HashSet for O(n)
Mistake 4: Not checking if sequence start
❌ Wrong:
for (int num : nums) {
int length = 1;
while (set.contains(num + 1)) { ... }
}
✓ Right: Check if num-1 exists first
Mistake 5: Integer overflow in num+1
❌ Wrong: Not considering Integer.MAX_VALUE
✓ Right: Use long or check bounds (rare in practice)
Mistake 6: Modifying set while iterating
❌ Wrong: Remove elements during iteration
✓ Right: Just read from set, don't modify
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Sorting
Time: O(n log n)
Space: O(1)
Use: When O(n log n) acceptable
Issue: Violates O(n) requirement
Approach 2: HashSet (OPTIMAL)
Time: O(n)
Space: O(n)
Use: Required for this problem
Benefit: Meets time complexity requirement
🔑 The Core Insight
Key observation: Only count from sequence STARTS
Sequence start detection:
→ num is start if (num-1) NOT in set
Why O(n) time:
- Build set: O(n)
- Each number checked as start: O(n)
- Each number counted in sequence: O(1) amortized
- A number is only counted once (as part of its sequence)
Total: O(n) + O(n) = O(n)
The trick: Skip non-start numbers!
→ 2 is not a start if 1 exists
→ 3 is not a start if 2 exists
→ Only count from 1 (the start)
🎯 Pattern Recognition
Problem Type: Finding Consecutive Elements
Core Pattern: HashSet for O(1) lookup + Smart iteration
When to Apply:
✓ Need to find consecutive sequences
✓ Array is unsorted
✓ O(n) time required
✓ Duplicates may exist
✓ Order doesn't matter
Key Techniques:
→ HashSet for O(1) contains check
→ Sequence start detection (num-1 not in set)
→ Count forward from starts only
→ Amortized O(n) analysis
Related Problems:
- Binary Tree Longest Consecutive Sequence (LC 298)
- Longest Consecutive Sequence II (LC 549)
- Minimum Number of Operations to Make Array Continuous (LC 2009)
🧠 Interview Strategy
Step 1: "Need longest consecutive sequence in unsorted array"
Step 2: "Sorting works but is O(n log n) - not O(n)"
Step 3: "Key insight: use HashSet for O(1) lookup"
Step 4: "Only count from sequence starts (num-1 not in set)"
Step 5: "Each number visited at most twice → O(n) total"
📝 Quick Revision Notes
🎯 Core Concept:
Use HashSet for O(1) lookups. Only count sequences from their start (when num-1 not in set). Count forward from each start.
⚡ Quick Implementation:
public int longestConsecutive(int[] a) {
if(a.length == 0) {
return 0;
}
// // Approach 1 - sort and find the length of LCS
// Arrays.sort(a); // 100,4,200,1,3,2 -> 1,2,3,4,100,200
// int res = 1;
// int count = 1;
// for(int i = 1; i < a.length; i++) {
// if(a[i] == a[i - 1] + 1) {
// count++;
// } else if (a[i] == a[i - 1]) {
// continue;
// } else {
// res = Math.max(count, res);
// count = 1;
// }
// }
// return Math.max(count, res);
// Approach 2 - hashing
Set<Integer> set = new HashSet<>();
for(int num : a) {
set.add(num);
}
// You need to start the count from lowest number in the LCS.
// So, if we find a number (curr - 1) less than current number (curr), skip the curr
// and wait till (curr - 1) is not found.
int count = 0;
int res = 0;
for(int num : set) {
// there is a sequence exists. Hence, skip
if(set.contains(num - 1)) {
continue;
} else {
count++; // count the current one
num++; // find for the next one if exits and increment the count
while (set.contains(num)) {
count++;
num++;
}
// once done, update res
res = Math.max(count, res);
count = 0;
}
}
return res;
}
🔑 Key Insights:
- HashSet enables O(1) lookups
- Sequence start:
num-1not in set - Only count from starts to avoid redundancy
- Each number visited at most twice (once as start check, once in counting)
- O(n) time amortized - meets requirement!
- Duplicates handled automatically by HashSet
- Order irrelevant - algorithm finds sequences regardless
🎪 Memory Aid:
"Start from the beginning (num-1 missing), count forward!"
Think: "Skip if not start, count once per sequence"
Related Patterns
- Binary Tree Longest Consecutive Sequence (LC 298)
- Longest Consecutive Sequence II (LC 549)
- Minimum Operations to Make Array Continuous (LC 2009)
Happy practicing! 🎯