Longest Consecutive Sequence
MediumArrays and hashing
The values in nums are in no order. Find the longest run of consecutive integers, such as 4, 5, 6, 7, whose every value is somewhere in nums, and return its length.
Aim for O(n) time.
Examples
Input: nums = [9, 1, 7, 3, 8, 2, 30, 10] Output: 4
7, 8, 9 and 10 are all present. 1, 2, 3 is a shorter run, and 30 stands alone.
Input: nums = [5, 5, 6, 6] Output: 2
Repeats do not make a run longer: 5, 6 is two long.
Constraints
0 ≤ nums.length ≤ 10⁵-10⁹ ≤ nums[i] ≤ 10⁹
Stuck?
Hint 1
Put every value in a Set. A run can only start at a value whose predecessor, value - 1, is missing.
Hint 2
From each such start, count upward while the next value is in the Set. Each value is then counted once, so the whole thing is O(n).
The idea
Every run has exactly one start: a value whose predecessor is missing. Put the values in a Set and count upward only from those starts. Each value is then counted once, inside its own run, so the search is O(n) with no sort.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
The Set tells you whether a value is present in constant time. It also drops repeats, which add nothing to a run.
function longestConsecutive(nums) { const values = new Set(nums); let best = 0; for (const n of values) { if (values.has(n - 1)) continue; let length = 1; while (values.has(n + length)) length++; best = Math.max(best, length); } return best;}The trap
Sorting and counting how many values in a row go up by one is correct when the values are all different, though it takes O(n log n). A repeated value breaks it: the repeat is not one more than the value before it, so the count starts over at 1 in the middle of a real run.
function longestConsecutive(nums) { const sorted = [...nums].sort((a, b) => a - b); let best = 0, run = 0; for (let i = 0; i < sorted.length; i++) { run = i > 0 && sorted[i] === sorted[i - 1] + 1 ? run + 1 : 1; // a repeat restarts the run best = Math.max(best, run); } return best;}