How do you find the length of the longest consecutive sequence in an unsorted array in O(n)?
Put all numbers in a set. Only start counting from a number whose predecessor is not in the set, then walk upward while the next number exists. Each number is visited at most twice.
Explain it simply
Think of students holding roll numbers in a random order. You want the longest run like 1, 2, 3, 4. Sorting would cost O(n log n), but a set lets you ask "is the number just before me present?" instantly.
If it is, you are in the middle of a run and can ignore yourself. If it is not, you are the start of a run, so count upward: x, x+1, x+2 and so on while they exist.
Example
function longestConsecutive(nums) {
const set = new Set(nums);
let best = 0;
for (const n of set) {
if (set.has(n - 1)) continue; // not the start of a run
let length = 1;
while (set.has(n + length)) length++;
best = Math.max(best, length);
}
return best;
}
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // Output: 4
console.log(longestConsecutive([])); // Output: 0Complexity
Time O(n), space O(n).
What to say in the interview
"I load everything into a set and only begin counting at numbers with no predecessor. From each start I extend while the next number exists. Every element is touched a constant number of times, so time is O(n) and space is O(n)."
Common mistakes
- Starting a count from every number, which becomes O(n squared) on long runs.
- Sorting first and then forgetting to skip duplicates.