Leetcode diary: 128. Longest Consecutive Sequence

#javascript #algorithms #devjournal #motivation

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

I liked this question cause it practices math magic for me. Whenever there is an array of integer, there is always some kind of optimal solution that relies on some brain teaser logic with the integers. I fucking hate it, it's the worst :(

So the question is, given an array of integers, find the longest sequence. Sequence as in 1,2,3,4,5. So the +1 or -1 chain. The problem specifies that you want to do an O(n) algorithm, so that immediately rules out sorting. The problem is too easy if you can sort lol...

So let's run through the possible techniques ...
1.) two pointers: not exactly... when you use this technique you'd have to rely on some other information so that you can decrement/increment left and right pointers to get some kind of order or pattern. Since the array is completely random, there is nothing you can do with this.

2.) prefix sum: this sounded possible but not really in this case. Prefix sum technique helps when you can get some information when you iterate through the array.
like A+B+C+D+E - A+B = C+D+E. You either need the information from A+B or C+D+E, like you need the sum to match to something. What we want is a sequence, not the sum. Although there is a sum formula from 1 to n, it is not helpful anyways since C+D+E could have a random number in between.

So what could we do? Well for one, we know that any sequence is [i..j], where we have all the numbers between i and j, which means there is i+1, i+1+1, i+1+1+1 ... j in random order throughout the array. This is helpful since when we iterate through the array, we'll meet number i somewhere. Then we'll eventually meet i+1 later in the array. It may be that we meet i+5 first or i+3 first, but that doesn't matter, the thing we are sure of is that for any i, we'll meet i+1 for sure if both exist in the array; vice versa true as well.

So, if we remember that there is i, it means when we meet i+1, we can somehow connect them together. So what this becomes is a graph problem, we just need to construct a graph representation from the array. I was inspired by what I watched in this video

The code is below:

var longestConsecutive = function(nums) {
    const map = {};
    nums.forEach(function(num){
        if(!map[num]) map[num] = [];
        if(map[num+1]) {
            map[num].push(num+1);
            map[num+1].push(num)
        }
        if(map[num-1]) {
            map[num].push(num-1);
            map[num-1].push(num)
        }
    });
    let maxConsec = 0
    const visited = {};
    Object.keys(map).forEach(function(num){
        if(!visited[num]) {
            maxConsec = Math.max(maxConsec, travel(num));
        }
    })

    function travel (num) {
        visited[num] = true;
        let neighbors = 1;
        map[num].forEach(function(neighbor){
            if(!visited[neighbor]) {
                neighbors += travel(neighbor)
            }
        });

        return neighbors;
    }

    return maxConsec
};

The for loop constructs the graph representation.

The second for loop walks through each number in the graph if it has not been visited yet. In the recursion, we travel more into its neighbors and return the number of neighbors each recursion has visited. The final return by the recursion is the total number of numbers in the sequence.
Although there is double for loop and a recursion, the final time complexity is still O(n) because the visited map prevents any revisit.

So happy to solve this question, maybe I am starting to see some light at the end of array integer tunnel <3

Let me know anything on your mind after reading through this, THANKS!