#128 Longest Consecutive Sequence

Given an unsorted array of integers numbers, determine the length of the longest sequence where the integers appear consecutively, meaning the numbers follow one another without any gaps.

Input

  • numbers: number[]: An array of integers

Notes

  • Solution should have a time complexity of O(n)

Examples

Input: numbers = [5,1,-4]Output: 1
Explanation: No consecutive numbers exist, 
so the longest consecutive sequence is any single number, giving a length of 1
Input: numbers = [1,-1,-1,-4,-5]Output: 2
Explanation: The consecutive sequences are [1], [-1], [-5, -4]. 
The longest is [-5, -4], with a length of 2
Input: numbers = [1,-1,0,8,11,10,9,9]Output: 4
Explanation: The longest consecutive sequence is 8, 9, 10, 11, with a length of 4 

怎麼解

export default function longestConsecutiveNumberSeq(numbers) {
  // first one is sort and if next one is not equal with cuurent + 1
  // second is a Set and to check if current + 1 exist
  let len = numbers.length;
  if (len < 2) return 1;
  let lookup = new Set(numbers);
  let longest = 1
  for(let i=0; i<len; i++){
    let currentStreak = 1
    let currentNum = numbers[i]
    while(lookup.has(currentNum + 1)){
      currentStreak++
      currentNum++
    }
    longest = Math.max(longest, currentStreak)
  }

  return longest

Last updated

Was this helpful?