#128
Longest Consecutive Sequence
Medium HashSet, start only at run starts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the length of the longest run of consecutive integers (like 4, 5, 6, 7) found in an unsorted array, in O(n).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest run like 4, 5, 6, 7 hidden in an unsorted array, in O(n).
Why this works: only start counting from x when x - 1 is missing (x starts a run). Each number is then counted once.
Example: [100, 4, 200, 1, 3, 2]
1 starts a run: 1, 2, 3, 4 → length 4100 and 200: length 1 each
✦Hints open one at a time
Put everything in a HashSet.
Only start counting from x when x − 1 is NOT in the set — x is the start of a run.
↗Approach
For each run start, count upward while x + 1, x + 2, … exist. Each number is visited by at most one count, so the total work is O(n).
</>Solution (Java)
import java.util.*;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue; // not a run start
int len = 1;
while (set.contains(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
}!Common mistake
Counting upward from every number, which makes it O(n²) on one long run.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon