128. Longest Consecutive Sequence

Ofcourse you can solve this question with a simple sort and iteration.

• sort the array
• iterate and keep track of the longest consecutive by checking if curr+1 exists and adding to maxLength

This however is O(nlogn) and leetcode demands better!

Initially I thought of creating a map in which I store all the numbers and their positions. Then on each number I could have another while loop to check if there is a consecutive sequence:

var longestConsecutive = function(nums) {

    /*
        hashmap of the num and position
        in loop check if num+1 is present and add to array
        have a max array and compare lengths
    */
    
    var m = new Map();
    var max = 0;
    for(var i = 0; i < nums.length; i++){
        if(!m.has(nums[i])){
            m.set(nums[i], i)
        }
    }
    for(var i = 0; i < nums.length; i++){
        var currLen = 1
        var next = nums[i]+1
        while(m.has(next)){
            next++
            currLen++
        }
        max = Math.max(currLen, max)
    }
    return max
};

This worked on 69/74 cases

Leetcode demands BETTER!

There were two small tweeks

1. use a set for unique nums
2. optimize the number of while loops needed to check the sequence

The above code goes into the loop for all the following:

nums = [100,4,200,1,3,2]
for i = 1: while loop checks 1->2->3->4
for i = 2: while loop checks 2->3->4
for i = 3: while loop checks 3->4

To avoid this we need to find a pattern for the start of the sequence:

The start of the sequence is the only number that does not match

!m.has(nums[i]-1 // there is no left element in the seq for the first num

The new code is updated to:

var longestConsecutive = function(nums) {

    var m = new Set(nums);
    var max = 0;
    
    for(var i = 0; i < nums.length; i++){
        var currLen = 1
        var next = nums[i]+1
        if(!m.has(nums[i]-1)){
            while(m.has(next)){
                next++
                currLen++
            }
            max = Math.max(currLen, max)
        }
        
    }
    return max
};

now go and try it for yourself and let me know if there are any more improvements I can make!