Longest Consecutive Sequence

Question

This task is taken from Leetcode -

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in \$O(n)\$ complexity.

Example:

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

Output: 4

/** Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. */

My solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
  const set = new Set(nums);
  let longestStreak = 1;
  let max = 0;
  set.forEach(x => {
    if (!set.has(x - 1)) {
      let num = x;
      while(set.has(++num)) { ++longestStreak; }
      max = Math.max(max, longestStreak);
      longestStreak = 1;      
    }
  });
  return max;
};

Time complexity is \$O(2n)\$ which is still in the range of \$O(n)\$ time complexity.

Answer 1

num is only used within the while loop and not outside of it. A for loop is more appropriate for such pattern.

The solution looks as if you forgot to perform a final refactoring to clean things up. The function starting with let longestStreak = 1; looks like a good idea, as the exercise is looking for the longest streak, and at this point, my expectation is that this variable will be probably returned at the end. But no, to my surprise it is reset to 1 in the forEach, and at the end the function returns max.

All that to say, it would make more sense to use a local length variable inside the forEach, and update longestStreak when a higher value is found, and return it at the end.

var longestConsecutive = function(nums) {
  const set = new Set(nums);
  let longestStreak = 0;
  set.forEach(x => {
    if (!set.has(x - 1)) {
      let length = 1;
      for (let num = x + 1; set.has(num); num++) { ++length; }
      longestStreak = Math.max(longestStreak, length);
    }
  });
  return longestStreak;
};