Longest Consecutive Sequence | LeetCode 128

AFFILIATE LINKS

Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

In this problem, we add each number to a set in order to remove any duplicate values. Then, we loop over the set only. To be the most efficient, we should only check the length of the streak once for each number. We do this by checking if the number that’s one less than the current number is also in the set. Think of it this way. If we have the numbers 3, 4, and 5, the number 5 will be in the streak [5], the streak [4, 5], and the streak [3, 4, 5]. By checking if the number that’s one less than the current number is in the set, we are checking if it captured in a different streak. If it is, we can move on to the next number in the set because the current number will be, or has already been, captured in a different streak (so there’s no reason to waste time by checking the length of its streak on this iteration).

Next, we check the length of the streak. We do this by checking if the number that’s one greater than the current number is in the set. If it is, we increment the count of our current streak by one, and again check if the number greater than our new number is in the streak. We do this over and over until the streak is done. Once it’s done, we compare the length of the current streak to the length of the longest streak. If it is longer than the longest streak, we update the value of the longest streak to be the length of the current streak.

Here is the full implementation

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let set = new Set();
    for (let num of nums) {
        set.add(num); // add all numbers to a set to remove any duplicates
    }

    let longestStreak = 0;

    for (let num of set) { // iterate over the set (not the original array) to ensure all numbers are unique
        
        /* if the number that's one less than the current number is in the set,
            we can skip the current number since it will be captured in a different
            streak */
        if (!set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1; // reset the current streak with each new loop

            /* increment the current number by one until we find the end of the streak */
            while (set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            // reset the longest global streak to the current streak if the current streak is greater
            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
};