Longest consecutive subsequence
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
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;}