intro⌗

Let’s start off today’s article with a couple of definitions:

  1. sequence: commonly defined as a list containing elements that follow each other in order. Such as [1, 2, 3, 4]
  2. O(n): a generic measurement of time that says that the operation will take as big as N is. So, if the value is 5, the operation will take 5 units of time.
  3. unsorted array: the opposite of a sorted array, instead of [1, 2, 3, 4], you’d have [4, 2, 1, 3]

Okay, let’s back to the main issue at hand. Instead of going about this solution with wanting to accomplish O(n), I’d rather go after the inefficient solution and then work our way towards the golden O(n)

inefficient solution⌗

Well, if you have an unsorted array, why don’t you sort it first, then deal with it later. In the language I am using which is Javascript, you could easily sort through an array of integers through the function sort().

[1, 5, 2, 0, 4].sort()
// [0, 1, 2, 4, 5]

Afterwards, you can loop over the items twice, get the local longest consecutive sequence, compare it to the global longest consecutive sequence and you’re done.

function solve(arr) {
    arr = arr.sort();
    var max = 1;
    // first loop
    for(let i=0; i < arr.length; i++) {
        var last = arr[i]
        var loopMax = 1;
        for(let j=i+1; j < arr.length; j++) {
            if(last == arr[j]-1) {
                last = arr[j];
                loopMax++;
                if(loopMax > max) {
                   max = loopMax;
                }
            } else {
                break;
            }
        }
        
        last = arr[i]
    }
    
    return max;
}

efficient solution: trade time for space⌗

While the inefficient solution uses at most 3 or 4 extra variables, this solution uses O(n*2) of space but, more importantly, O(n) of time.

Here are the steps to accomplish the solution:

  1. do not sort the array
  2. create a map to store consecutive sequence number for each number
  3. check the number behind each two numbers, i.e if x = 2, check for 1 and 3’s values in the map
  4. if they exist: search for the previous and next numbers in the map, connect them and set them to same value
  5. if not, create an entry in map equal to 1, since consecutive sequences start at 1
  6. compare this number’s consecutive sequence to the previous one, and if it’s larger set the previous one to the new one.

Here’s how the code would look:

function solve(arr) {
    var m = new Map();
    var max = -1;
    
    for(var i in arr) {
        var curr = arr[i];
        console.log(curr)
        
        var prev = curr - 1
        var next = curr + 1;
        
        var obj = null;
        if(m.get(prev) !== undefined) { 
            obj = m.get(prev);
            obj.num += 1
        }
        
        if(m.get(next) !== undefined) {
            if(obj !== null) {
                obj.num += m.get(next).num;
                m.set(next, obj)
            } else {
                obj = m.get(next);
                obj.num += 1
            }
        }
        
        if(obj === null) {
            obj = {num: 1}
        }
        
        m.set(curr, obj);
        if(max < obj.num) {
            max = obj.num;
        }
    }

    return max
}

The reason this works is that the map keeps track of the consecutive sequence through the use of objects. So, if 3 numbers are in a sequence, modifying one number’s field modifies every single number num field in the sequence.

personal notes⌗

This problem was one of the most fun problems I’ve done in a while, it strkes that perfect balance between hard enough to be challenging but not too hard to be disheartening. I am glad I came up with the solution without seraching it on google.