15. Longest Consecutive Sequence
Given an unsorted integer array nums, return the length of the longest run of consecutive integers (x, x+1, x+2, …) whose values all appear in nums. The values may appear anywhere in the array, in any order, and duplicates count only once.
Your algorithm must run in O(n) time.
Input: nums = [50,3,52,1,2,51,4] Output: 4
Explanation: The values 1, 2, 3, 4 form the longest run; 50, 51, 52 has length 3.
Input: nums = [6,2,9,2,4,3,5,7,1] Output: 7
Explanation: 1 through 7 are all present (the repeated 2 does not matter). 9 is on its own.
Input: nums = [] Output: 0
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
💡 Hint 1
Sorting makes the runs easy to see, but it costs O(n log n). What gives you O(1) membership checks instead?
💡 Hint 2
Put every value into a hash set. A run can only start at a value x for which x - 1 is not in the set.
💡 Hint 3
From each run start, count upwards while x + 1, x + 2, … are in the set. Each value is visited by at most one such count, so the total work is O(n).
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Load all values into a hash set. A value x begins a run only if x - 1 is absent; for each such start, walk upwards through x + 1, x + 2, … while they are in the set and record the run length. Values that are not run starts are skipped immediately, so every value is stepped over by at most one walk and the whole algorithm is linear. Iterate over the set rather than the array so duplicates do not trigger repeated walks.
function longestConsecutive(nums) {
const set = new Set(nums);
let best = 0;
for (const x of set) {
if (set.has(x - 1)) continue;
let len = 1;
while (set.has(x + len)) len++;
best = Math.max(best, len);
}
return best;
}class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue;
int len = 1;
while (set.contains(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @return {number}
*/
function longestConsecutive(nums) {
}Run your code to see results here.