Longest Consecutive Sequence
Problem
nums. Return the length of the
longest run of values x, x+1, x+2, … that all appear in the array (in any
positions). Duplicates count once. The intended solution runs in O(n) time.[100,4,200,1,3,2]Output4 (1,2,3,4)[0,3,7,2,5,8,4,6,0,1]Output9[]Output00 ≤ n ≤ 105 · -109 ≤ nums[i] ≤ 109 · Required: O(n) time.
Try it yourself
class Solution {
public int longestConsecutive(int[] nums) {
}
}
x whose predecessor x-1 is
absent — it is a sequence start. Each run is then walked exactly once, so the total
work is O(n) with a hash set.Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].
Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.
Open the Hashing & Counting guide →Approaches
Brute ForceExtend Every Number with Linear Search
O(n3)Space O(1)Treat every element as a possible start and keep asking “is
x+1 in the array?” by scanning it. A run of length L costs
L scans of O(n), and we may do this for all n starts.
public int longestConsecutive(int[] nums) { int best = 0; for (int num : nums) { int cur = num, streak = 1; while (contains(nums, cur + 1)) { cur++; streak++; } best = Math.max(best, streak); } return best; } private boolean contains(int[] nums, int target) { for (int x : nums) if (x == target) return true; return false; }
Correct and memory-free, but cubic — hopeless for n = 105.
BetterSort, then Count Runs
O(n log n)Space O(log n)After sorting, a consecutive run sits in adjacent cells. Walk once: equal
neighbour → skip (duplicate), neighbour +1 → extend the streak,
anything else → reset to 1.
public int longestConsecutive(int[] nums) { if (nums.length == 0) return 0; Arrays.sort(nums); int longest = 1, current = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) continue; // duplicate if (nums[i] == nums[i - 1] + 1) { current++; } else { longest = Math.max(longest, current); current = 1; } } return Math.max(longest, current); }
Simple and fast in practice, but sorting breaks the O(n) requirement (and mutates input).
OptimalHashSet — Grow Only from Sequence Starts
O(n)Space O(n)Put all numbers in a HashSet for O(1) lookups. A number is a
start only if num-1 is missing; from each start walk
num+1, num+2, …. Every element is visited by at most one walk, so the
inner while totals O(n) across the whole loop.
public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) set.add(num); int longest = 0; for (int num : set) { if (!set.contains(num - 1)) { // num starts a run int cur = num, streak = 1; while (set.contains(cur + 1)) { cur++; streak++; } longest = Math.max(longest, streak); } } return longest; }
Linear time — meets the requirement at the cost of O(n) memory.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Extend Every Number with Linear Search | O(n3) | O(1) |
| Better | Sort, then Count Runs | O(n log n) | O(log n) |
| Optimal | HashSet — Grow Only from Sequence Starts | O(n) | O(n) |
- Starting a walk from every number (no
num-1check) — silently becomes O(n2). - Sorting version: not skipping duplicates resets the streak on
[1,2,2,3]. - Returning 1 for an empty array — the answer is 0.
- Mention sorting first, then note it violates the O(n) requirement.
- Justify O(n) with amortised analysis: each element is walked over at most once.
- Union-Find also works (union x with x±1) — mention it as an alternative.