128. Longest Consecutive Sequence

Link: https://leetcode.com/problems/longest-consecutive-sequence

Description: Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity.

Solution:

Create a hash table to store the numbers. Then iterate through the array and check if the current number is the starting point of a consecutive sequence we need this to reduce the time complexity to O(n). If it is, we call a helper recursive function to find the length of the sequence. We update the max length if the new sequence is longer than the previous one.

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  const obj = {}
  let max = 0

  for (const n of nums) {
    obj[n] = true
  }

  for (const n of nums) {
    // check if n is starting point of consecutive sequence
    const hasPrevious = obj[n - 1] === true
    if (hasPrevious) {
      continue
    }
    const newCurrent = helper(0, obj, n)
    max = Math.max(max, newCurrent)
  }

  return max
}

function helper(val, obj, n) {
  val += 1
  if (obj[n + 1]) {
    return helper(val, obj, n + 1)
  }
  return val
}