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.

2025

This is what I came up with:

function longestConsecutive(nums: number[]): number {
    const s = new Set(nums)
    let longestSequence = 0
 
    for (let num of s){
        // If number doesn't have a left neighbor anywhere in nums
        // it is its own sequence
        if (!s.has(num-1)){
            let offset = 1
            while (s.has(num+offset)){
                offset++
            }
            longestSequence = Math.max(longestSequence, offset)
        }
    }
    return longestSequence
};

Mistake 1 This line got me for a second: longestSequence = Math.max(longestSequence, offset-1)

I originally moved this line around a bit and thought I needed to add -1 but then realized I did not - if !s.has(num-1) then for that number, the sequence length will always be 1.

Of course, longestSequence could also just be set to 1 to begin with - unless there are empty arrays.

But this works well.

Mistake 2 The second thing was that originally I was iterating through nums, and I was exceeding time. That seems sort of arbitrary, but apparently there can be duplicates. So, if we want to skip them we’ve already done the work, we can iterate directly through our set instead since the duplicates aren’t actually a relevant signal to us.