Longest consecutive subsequence

Medium

Problem

Given an unsorted array of integers, return the length of the longest run of consecutive values (x, x+1, x+2, …). The values can appear in any order in the array. Aim for O(n) time.

Example 1

Input:  [100, 4, 200, 1, 3, 2]
Output: 4

The run 1, 2, 3, 4.

Also asked as: Find longest coinsecutive subsequence

Test cases

Case 1

Input:    [100,4,200,1,3,2]
Expected: 4

Case 2

Input:    [0,3,7,2,5,8,4,6,0,1]
Expected: 9

Case 3

Input:    []
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Hash set, count from sequence starts

Time O(n)Space O(n)

Put all values in a set. A value begins a run only if value−1 is absent; from there count upward.

function longestConsecutive(nums) {
const set = new Set(nums);
let best = 0;
for (const n of set) {
if (set.has(n - 1)) continue;
let len = 1;
while (set.has(n + len)) len++;
best = Math.max(best, len);
}
return best;
}