Coding Interview Prep: Longest Consecutive Sequence with Solution

Solution

/*
Time Complexity: O(n)
Space Complexity: O(n)
Runtime: 64 ms
*/
var longestConsecutive = function(nums) {
    const numSet = new Set(nums);
    let longest = 0;

    for (let n of nums) {
        if (!numSet.has(n - 1)) {
            let length = 1;

            while (numSet.has(n + length)) {
                length++;
            }

            longest = Math.max(longest, length);
        }
    }

    return longest;    
};

First, a set is created with the array nums. Initialize a variable called longest that will be the longest consecutive sequence. Create a for loop to iterate through each element in the array. Check the value right before the current value by checking if the value-1 is in the set. If value-1 is not in the set, then create a while loop to check if value+length is in the set. If it is in the set, increase length by 1 every time. Outside the while loop, find the max between the current longest and the calculated length.

This method will be a time complexity of O(n) because there is 1 for loop that iterates through each value in the array. The space will be O(n) because of the creation of the set.