Longest Consecutive Sequence

Given an array of elements, find a subsequence in the array such that all the elements in the sequence are consecutive irrespective of their order.

Example

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

Output:
4
// LCS [1, 2, 3, 4]

Solution 1: By sorting the array.

Conceptually this is how it will work.

• First, filter the array and get only unique elements from it.
• Then sort the array using any efficient sorting algorithm in any order.
• Now, traverse the array and in each iteration check if the previous element in the array is greater than or less than the current element (consecutive) depending upon how the elements in the array are sorted. If yes then increment the count of subsequence.
• At the end return the longest subsequence.

const LCS = (arr) => {
  //get unique
  arr = [...new Set(arr)];
  
  //sort
  arr = arr.sort((a,b) => a - b);
  
  let max = 0;
  let count = 0;
      
  // find the maximum length
  // by traversing the array
  for (let i = 0; i < arr.length; i++) {

    // check if the current element is
    // equal to previous element +1
    if (i > 0 && arr[i] === arr[i - 1] + 1){
      count++;
    }
    else{
      count = 1;
    }

    // Update the maximum
    max = Math.max(max, count);
  }
  
  return max;
}

Input:
const arr = [100,4,200,1,3,2];
console.log(LCS(arr));

Output:
4

Time complexity: O(nlogn).
Space complexity: O(n).

---

Solution 2: Longest consecutive sequence using set.

Conceptually this is how it will work.

• Copy all the elements of the array in a set.
• Iterate the array and in each iteration determine if the current element will lead to new subsequence by checking if there is no element less than the current, present in the set.
• Then find how long this subsequence can be by incrementing the count till there is consecutive elements in the set.
• In the end return the longest consecutive sequence.

const LCS = (arr) => {
  //get unique elms  
  const S = new Set(arr);
  
  //store the result
  let max = 1;
  
  // iterate array elements
  for (let e of arr) {
    
    // if the current element begins a new seq
    if (!S.has(e - 1)) {
      
      // tracks the length of subsequence
      let len = 1;

      // count all the elements of the subsequence
      // e+1, e+2,...
      while (S.has(e + len)) {
        len++;
      }

      // get the max subsequence
      max = Math.max(max, len);
    }
  }

  return max;
}

Input:
const arr = [0,3,7,2,5,8,4,6,0,1];
console.log(LCS(arr));

Output:
9

Time complexity: O(n).
Space complexity: O(n).