Longest Consecutive Sequence

This is short walk through on how to solve the longest consecutive sequence Leetcode problem #128.

The problem:

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

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Based on the two examples above you can see that the array is not in order and it may also have duplicates.

Since we are looking for a consecutive pattern. We do not need the duplicate numbers. So our first step will be to remove the duplicates and we can achieve that with Set().

let set = new Set()    
for(let num of nums) {
        set.add(num)
    }

Now set variable consists of a list of unique numbers.

We want iterate through that list of numbers in the set and see if that current number has num + 1. Because if it does then we want to add a += 1 to the streak count. For example: [100,4,1,2,3]

For num = 100(index 0)
Does set have 100 + 1 = 101? No it does not so that sequence only consists of 1 number. since it doesn’t go up.

Now let’s ask this for all the remaining numbers in that list.

For num = 4(index 1)
Does set have 4 + 1 = 5? No it does not so that sequence only consists of 1 number. since it doesn’t go up.

For num = 1(index 2)
Does set have 1+ 1 = 2? Yes it does so that sequence will += 1 bringing the total counter of that sequence to 2. And we will continue until the answer to this question becomes No. Which is when we will break and continue to check the rest of the list.

Now as you may have noticed the rest of the list meaning numbers 2 and 3. Will also have a sequence but the sequence at index 2 which is number 1 will be the longest. So the question is how to avoid going through various sequence that are part of the same ones.

Well instead of just asking if num + 1 is in the set we should also check is num — 1 is in the set as well. If it is then this means this number is part of another sequence within this list.

Now taking all of this in consideration this is what the resulting code will look like.

longestConsecutive = (nums) => {
    let set = new Set()    
    for(let num of nums) {
        set.add(num)
    }    
    
    let longestSeq = 0    
    for(let num of set) {
         if (!set.has(num - 1)){
            let currentNum = num
            let currentSeq = 1            
         
            while (set.has(currentNum + 1)) {
                currentSeq += 1
                currentNum += 1
            }
            longestSeq = Math.max(longestSeq, currentSeq)
        }
    }
}

This code will ask both questions and focus on the longest consecutive sequence.

Hope this helps!