Javascript Solution `Longest Consecutive Sequence` Problem

Given an array containing N integers, find length of longest band.

A band is defined as a subsequence which can be re-ordered in such a manner all elements appear consecutive (ie with absolute difference of 1 between neighbouring elements)

A longest band is the band (subsequence) which contains maximum integers.

For exact problem visit Leetcode Link;

Sample Input Output

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

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9

Input: [1, 1, 1, 1, 2, 3]
Output: 3

Solution Approach

There are many approach to solve this problem.

We will discuss TC O(N) approach.

Important: For any value i We will not check if nums[i]=nums[i+1] unless num[i] is the left most element of Consecutive subsequence.

1. First we created a look-up map h using javascript object literals. It will hell help us to check if a number exist or not in O(1) time.

2. Then we will iterate for all keys of h.

   For any key num if it is left most element of Consecutive subsequence then we will count all consecutive number and update ans else we move to the next element i+1.

3. After doing step-2 for all element we will return ans.

Time Complexity: O(N)

Space Complexity: O(N)

Javascript Implementation

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

  // Created a lookup map
  // It will help to remove duplicate nums and
  // we can check if any num exist or not in O(1) Time.
  nums.forEach((num) => {
    h[num] = 1
  })

  for (let num in h) {
    // Here we are checking if num is left most element of our band/subsequence
    if (h[num - 1] === 1) continue

    let count = 0
    while (h[num]) {
      num++
      count++
    }
    ans = Math.max(ans, count)
    count = 0
  }
  return ans
}