Longest Consecutive Sequence: Smart Set-Based Approach
The Prompt
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.
Understanding the Problem
You want the longest run of consecutive integers (like 1, 2, 3, 4) hiding in an unsorted array. Sorting makes runs obvious but costs O(n log n), and the problem explicitly demands O(n) — so the sort is the baseline you must beat, not the answer.
Dump everything into a hash set and consecutive-ness becomes a membership question: given a number x, its run continues as long as x + 1, x + 2, ... are in the set. The danger is walking the same run once per member — that would be O(n²). The trick is deciding who is allowed to start a walk.
The Interview Flow
Interviewer
Your task is to find the length of the longest consecutive sequence in an unsorted array. For example, in `[100, 4, 200, 1, 3, 2]`, the longest sequence is `[1, 2, 3, 4]`, so the answer is 4. The solution must be O(n).
Candidate
The O(n) constraint rules out sorting, which would be O(n log n). This suggests using a data structure with O(1) average time lookups, like a hash set.
Interviewer
How would you use a hash set?
Candidate
First, I can put all the numbers from the array into a hash set to get O(1) lookups. Then, I can iterate through the numbers in the array again. For each number, I can check if it's the start of a sequence.
Interviewer
How do you identify the start of a sequence?
Candidate
A number is the start of a sequence if it doesn't have a left neighbor in the set. For example, for the number `4`, I check if `3` exists in the set. For `1`, `0` doesn't exist, so `1` is a start. By only starting my count from the beginning of a sequence, I ensure that I don't do redundant work.
Interviewer
And once you find a start?
Candidate
Once I find a starting number, I start a loop, checking for the next consecutive numbers (`num + 1`, `num + 2`, etc.) in the set, counting as I go. I keep track of the maximum length found across all sequences. This way, each number is visited at most twice (once for the main loop and once for the inner counting loop), resulting in an O(n) overall time complexity.
Interviewer
That's a very clever and efficient approach. Please implement it.
Why is checking "num − 1 not in set" enough for O(n)?
Only walk forward from a number whose predecessor is absent — that number is provably the leftmost element of its run. Every other member of the run gets skipped in O(1), because its num − 1 check hits the set. So each run is traversed exactly once, from its true start, and its full length is measured in one walk.
Total work: every element is visited at most twice — once by the outer loop (usually a constant-time skip) and at most once inside a single walk. That is O(n) time bought with O(n) space for the set; the sorted alternative flips the trade to O(1) space at O(n log n) time.
O(n) Solution using a Hash Set
- First, handle the edge case of an empty array by returning 0.
- Create a hash set and add all the numbers from the `nums` array to it. This allows for O(1) average time complexity for checking the existence of a number.
- Initialize a `maxLength` variable to 0.
- Iterate through each number `num` in the `nums` array (or the set).
- For each number, check if it is the start of a sequence. This is true if `num - 1` is NOT present in the hash set.
- If it is the start of a sequence, initialize a `currentLength` to 1 and a `currentNum` to `num`.
- Start a loop and check if `currentNum + 1` exists in the set. As long as it does, increment `currentLength` and `currentNum`.
- After the inner loop finishes, update `maxLength = max(maxLength, currentLength)`.
- After iterating through all numbers, `maxLength` will hold the answer. Return `maxLength`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function longestConsecutive(nums) {
if (nums.length === 0) return 0;
const numSet = new Set(nums);
let maxLength = 0;
for (const num of numSet) {
// Check if it's the start of a sequence
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentLength = 1;
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentLength += 1;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}Explanation
Trace nums = [100, 4, 200, 1, 3, 2], where the answer is the 4-long run 1, 2, 3, 4.
1Set = {100, 4, 200, 1, 3, 2}. num = 100: 99 is not in the set, so 100 starts a run. Walk forward: 101 missing → run length 1. (200 will behave the same.)
2num = 1: 0 is not in the set → a run starts. Walk: 2 ✓, 3 ✓, 4 ✓, 5 ✗. Length = 4, so maxLength = max(1, 4) = 4.
3num = 4, 3, and 2 are all skipped in O(1): each has its predecessor (3, 2, 1) in the set, so none is a run start. The 1-2-3-4 run was walked exactly once. Answer: 4.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.