3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ To downvoters: please explain your actions \$\endgroup\$ – thadeuszlay Jun 4 at 10:20
1
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ Good point on using the for-loop in this case, because it would eliminate the additional num variable. I try to use more while than for loops because while loops adds less complexity than for-loops. And creating a new variable, length, inside the loop is also a good idea because it makes resetting obsolete. Thanks for your review. \$\endgroup\$ – thadeuszlay May 26 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.