37) Longest Consecutive Sequence

Okay so this was the approach I went with off the bat:

function getLastFromMap(map: Map<number, number>): number {
  const arr = Array.from(map);
  return arr.length > 0 ? arr[arr.length - 1][1] : 0;
}
 
function longestConsecutive(nums: number[]): number {
    // A map that stores a key that is the next element in any given sequence, 
    // and when you find that element, it deletes that entry
    // and it adds an entry for the next element
    // But it increments the value every time
    // But this sounds more like a stack maybe
    // oh but I mean, maps are in order so
    // that should be fine
 
    const cMap: Map<number, number> = new Map()
 
    for (let i = 0; i < nums.length; i++){
        let num = nums[i];
        if (cMap.has(num)){
            const finds = cMap.get(num)
            cMap.delete(num)
            cMap.set(num+1, finds+1)
        } else {
            cMap.set(num+1, 1)
        }
    }
 
    return getLastFromMap(cMap)
};

But pretty quickly after writing it down realized that this only works in one direction of finding the next number in a sequence(and I’m not saying it quite does that yet). Whereas I need an algo that can keep track of numbers before and after. I mean it’s really just a case of encoding the human behavior of what we do when we are trying to construct a straight out of a group of cards in poker.

Here is a Claude generated result:

function longestConsecutive(nums: number[]): number {
    if (nums.length === 0) return 0
 
    const numSet = new Set(nums)
    let maxLength = 0
 
    for (const num of nums){
        if (!numSet.has(num-1)){
            let currentNum = num
            let currentLength = 1
 
            while (numSet.has(currentNum+1)){
                currentNum++
                currentLength++
            }
 
            maxLength = Math.max(currentLength, maxLength)
        }
    }
 
    return maxLength
};

What it does that’s really smart is it just checks to see if any consecutive numbers exists behind the current number, and if yes, then we simply don’t check that number.

This prevents us from needing to do a two-way check, would requires us to do tree-like movement.

I do think it would be kind of cool to concatenate the lengths of sequences we find that end up matching up. But also more complicated.