Given an unsorted array of integers nums, return the length of the longest run of consecutive integers — values that differ by exactly 1 from their neighbour in the run.
The numbers do not have to be adjacent (or in order) inside nums; only their values must be consecutive. Duplicate values count once.
Aim for an O(n) algorithm — fast enough that you never need to sort the input.
Example
The run [1, 2, 3, 4] has length 4. 100 and 200 are isolated.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Intuition
The most direct way to find the longest run of consecutive values is to sort the array, then walk it once: every time the next value is exactly one more than the previous, the current run grows; otherwise the run resets. Track the longest run seen. Sorting lines the values up so consecutive numbers sit next to each other, and a single pass measures every run.
function longestConsecutive(nums) {
if (nums.length === 0) return 0;
// Sort so consecutive values become adjacent.
const sorted = [...nums].sort((a, b) => a - b);
let longest = 1;
let run = 1;
for (let i = 1; i < sorted.length; i++) {
if (sorted[i] === sorted[i - 1]) continue; // duplicate counts once
if (sorted[i] === sorted[i - 1] + 1) {
run++; // extends the current run
} else {
run = 1; // gap — start a fresh run
}
longest = Math.max(longest, run);
}
return longest;
}This is O(n log n) — the sort dominates, and the prompt asks for O(n). Can we do better than sorting?
The only reason we sorted was to ask "is the next number present?" — but a hash set answers exactly that in O(1), no ordering required. Dump every value into a Set (which also drops duplicates for free), and consecutiveness becomes a membership test: a run containing n simply means n, n+1, n+2, … are all in the set.
The key observation that keeps this linear: only start counting a run from its smallest value — a value n whose predecessor n - 1 is absent from the set. Any value in the middle of a run has its predecessor present, so we skip it rather than re-walking the same run from the inside. That guard means each run is walked exactly once, and across all runs every value is visited at most twice — so despite the nested-looking while loop, the total work is O(n). This trading of O(n) space for O(1) lookups is the core hash maps move.
Walking it through:
set of nums = [100, 4, 200, 1, 3, 2] — walk forward only from run starts
100 is a run start (99 absent), but 101 is missing too — a lone run of length 1.
A skip step: 4 has predecessor 3 in the set, so it sits inside a run — don't start here.
1 is a run start (0 absent). Begin walking forward: length = 1, look for 2.
Walk 1 → 2 → 3 → 4 (all present, scattered across the lane), stop at the missing 5. Run length 4. longest = 4.
3 has predecessor 2 present — skip. Same for 2 (1 present). They were already counted by the walk.
Optimization
Hash set, walk from run starts
Sorting would give an O(n log n) answer, but a set lets us do it in O(n).
Put every value into a Set (this also drops duplicates). Then for each value n, only start counting if n - 1 is not in the set — that means n is the smallest number of its run, so we count each run exactly once. From a start, walk n, n+1, n+2, … forward while each is present and track the longest length.
Although there's a nested while loop, each value is visited by the inner walk at most once across the whole run, so the total work is O(n). The "only start from run beginnings" guard is what keeps it linear — without it, every element could re-walk its entire run.
O(n) time, O(n) space.
function longestConsecutive(nums) {
// O(1) membership tests; also collapses duplicate values to one.
const set = new Set(nums);
let longest = 0;
for (const n of set) {
// Only walk from a run's smallest value — if n-1 exists, n is mid-run,
// so skip it and let its run be counted from its own start (keeps it O(n)).
if (set.has(n - 1)) continue;
let length = 1;
let current = n;
// Extend forward through the run while the next value is present.
while (set.has(current + 1)) {
current++;
length++;
}
longest = Math.max(longest, length); // remember the longest run seen
}
return longest;
}Complexity analysis
Time complexity: O(n). Here's why:
- Building the
Setfrom the input is one O(n) pass. - The outer loop visits each distinct value once, doing an O(1)
has(n - 1)check. - The inner
whileonly runs for run starts, and it walks each value of a run at most once across the whole algorithm.
The nested while looks like it could make this O(n²), but the run-start guard means a value is touched by an inner walk only when its run is counted, once — so every value is visited at most twice total, and the overall time is O(n).
Space complexity: O(n). Here's why:
- The
Setholds up to one entry per distinct value, so it grows linearly with the input. - The loop itself uses only a few counters (
longest,length,current) — O(1).
That set is the price of dropping the time from the sort's O(n log n) to O(n): we spend O(n) extra space to buy O(1) membership tests.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [] | 0 | Empty array — no numbers, so the longest run is 0. |
| nums = [99] | 1 | Single element — a run of length 1 with no neighbours. |
| nums = [5,5,5] | 1 | All duplicates collapse to one value in the set — run of 1. |
| nums = [20,21,22,50,51] | 3 | Two separate runs; the longer is {20,21,22}, length 3. |
| nums = [9,1,4,7,3,2,6,8,5] | 9 | Shuffled 1..9 — order doesn't matter, the whole set is one run. |
| nums = [-10,-8,-9,-7,5] | 4 | Negatives — {-10,-9,-8,-7} form a run of 4; 5 is isolated. |
Try it yourself
Write your solution against the real judge before checking the reference.