What it teaches: Use a set to find where runs start (x − 1 absent), then count each run once: O(n) without sorting.
Practise it on judges as “Longest Consecutive Sequence”.
The problem
Given an unsorted integer array nums, return the length of the longest run of consecutive values (like 4, 5, 6, 7), in O(n) time. The values don't need to be next to each other in the array.
These clues point to Hash Map Lookup (Complement): As you scan, store what you've seen; for each new element, ask in O(1) whether its partner was already seen.
Stuck? Take one hint at a time
Solution.java · starter
import java.util.*;
class Solution {
public int longestConsecutive(int[] nums) {
return 0;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Sort, then walk counting runs, skipping duplicates and resetting on gaps.
Approach 1
import java.util.Arrays;
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Arrays.sort(nums);
int best = 1, run = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) continue;
run = (nums[i] == nums[i - 1] + 1) ? run + 1 : 1;
best = Math.max(best, run);
}
return best;
}
}
Verdict: Correct but misses the O(n) requirement.
2
Optimal: start runs only at their beginning
Time O(n) Space O(n)
Put all values in a set. For each value x in the set, skip it if x − 1 exists (it's in the middle of a run). Otherwise x starts a run: count x + 1, x + 2, ... while they exist.
Each value is counted inside exactly one run, so the total work is O(n) even though there's a loop inside a loop.
▶ Dry run: Only counting from run startsnums = [100, 4, 200, 1, 3, 2]
100
0
4
1
200
2
1
3
3
4
2
5
set(list)
1004200132
Step 1/5100: 99 is absent, so 100 starts a run. 101 is absent: length 1.
Approach 2
import java.util.HashSet;
import java.util.Set;
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 the start of a run
int len = 1;
while (set.contains(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
}
Verdict: Linear: every value is visited by at most one counting loop.
Before you submit
Edge cases and common mistakes
Test these inputs
Empty array → 0
Duplicates
Negative values
All values consecutive
Mistakes people make
Counting from every element, not only run starts: O(n²) for one long run.
Iterating over nums instead of the set: duplicates of a run start repeat the counting.