Coding · Hashing
Longest Consecutive Sequence
- Reported once
- Medium
- SDE (on-campus)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given an unsorted array of integers, return the length of the longest run of consecutive integers, where the numbers may appear anywhere in the array and in any order. For [100,4,200,1,3,2] the answer is 4, because 1, 2, 3 and 4 are all present. Duplicates count once, negative numbers and zero are allowed, and the array may be empty. Aim for linear time on arrays of up to a million values.
Restated in our own words, not a quote from Atlassian or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: can there be duplicates, and should they count once? Can values be negative or very large? How big can the array be, and is extra memory fine? Is a run required to be contiguous in the array (no, only in value)? What should an empty array return? Is O(n log n) acceptable or do we need linear?
I would assume duplicates count once, any 32-bit values, an empty array gives 0, and the target is O(n) time using extra memory, since sorting is the easy fallback I can mention.
Brute force
Say the obvious answer and why it is too slow.
The simplest approach is to sort the values and sweep once, resetting the run length at every gap. That is O(n log n) and perfectly correct, but it is not linear, and duplicates need care. In JavaScript the sort also needs a numeric comparator, because the default sort compares numbers as strings. Another common attempt is to put the values in a set and, for every value, count upward while the next number is present. That looks linear but is not: for the values 1 to n, the value 1 walks n steps, 2 walks n - 1 steps, and so on, which is O(n²).
The waste is that every member of a run re-counts the same run. Only the first member should do the counting.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²) counting, O(n log n) sorting
- Time
- O(n) average
- Space
- O(n)
The pattern is a hash set with counting from run starts. Put every value in a set. A value is the start of a run exactly when its predecessor, value minus one, is not in the set. Loop over the values, skip any that are not starts, and for each start walk upward while the next number is present. The length of that walk plus one is the run length, and the best one wins.
Why is this linear? The inner walk only runs from run starts, and runs do not overlap, so each value is walked at most once as part of exactly one run. Every value also appears once in the outer loop. That is at most two visits per distinct value, and every set lookup costs O(1) on average in JavaScript.
Why is it correct? Every run has exactly one start, the smallest value in the run, and from it the walk finds the whole run. A value that is not a start belongs to a run that is counted from its own start, so skipping it loses nothing.
I loop over the set, not over the original array. With duplicates, iterating the array would visit a start several times and repeat its walk, which could bring back O(n²) for something like many copies of the first element of a long run. Out loud: "only start counting where the number before is missing."
Walk it through
A dry run on the example, step by step.
| value | value-1 in set? | start? | run length | best |
|---|---|---|---|---|
| 100 | no (99) | yes | 1 | 1 |
| 4 | yes (3) | no, skip | - | 1 |
| 200 | no (199) | yes | 1 | 1 |
| 1 | no (0) | yes | 4 (1,2,3,4) | 4 |
| 3 | yes (2) | no, skip | - | 4 |
| 2 | yes (1) | no, skip | - | 4 |
The set is {100, 4, 200, 1, 3, 2}. Visit 100: 99 is absent, so it is a start; 101 is absent, so the run has length 1. Visit 4: 3 is present, so skip. Visit 200: a start with run length 1.
Visit 1: 0 is absent, so it is a start. Walk upward: 2, 3 and 4 are present and 5 is not, so the run has length 4 and the best becomes 4. Visit 3 and 2: both have predecessors present, so both are skipped. The answer is 4. The trace shows each value, whether it started a run, and the best so far.
The code
Runnable JavaScript, checked against test cases.
function longestConsecutive(nums) {
const present = new Set(nums);
let longest = 0;
for (const value of present) {
const isRunStart = !present.has(value - 1);
if (!isRunStart) continue;
let end = value;
while (present.has(end + 1)) end++;
longest = Math.max(longest, end - value + 1);
}
return longest;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Empty array: the loop never runs and the result is 0.
- Single value: it is a start with run length 1.
- Duplicates: the set stores each value once, so [5,5,5] gives 1 and [1,2,0,1] gives 3.
- Negatives and zero: only value - 1 is tested, so [-3,-2,-1] is a run of 3 with no special case.
- Huge gaps: values like 1,000,000,000 and 1 do not matter, since we never index an array by value.
- Already sorted or reversed: order of the input has no effect on the result.
Follow-ups to expect
Where the interviewer pushes next.
- Can you solve it with union-find instead, merging each value with its neighbours, and what is the cost?
- How would you return the run itself, not just its length?
- What if the numbers arrive one at a time and you must report the longest run after each one?
- How would you handle it when the data does not fit in memory?
Where candidates slip
The mistakes this problem punishes.
Common mistakes:
- Counting upward from every value, which is O(n²) on a long run.
- Sorting and comparing neighbours without deduplicating, so equal neighbours reset the run.
- Looping over the original array rather than the set, which repeats walks for duplicates.
- Using an array indexed by value, which fails on negatives and large gaps.
- Returning the last value of the run instead of its length, or being off by one.
- Testing value + 1 for the start check instead of value - 1.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.