Longest Consecutive Sequence

Question

You're given an unsorted list of integers. Your task is to find the length of the longest sequence of consecutive numbers (regardless of order).

For example, in the list [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so the result is 4.

Example

Input: [-2, 3, 7, 2, 5, 4, 6, -1, 1]

Output: 7

Explanation: The sequence is [1, 2, 3, 4, 5, 6, 7] → longest length is 7

Input: [100, 101, 102]

Output: 3

My Notes

Used a map to remove duplicates and allow O(1) lookup.
Sorted the keys to allow linear scan of consecutive numbers.
Compared current number to previous to track streak length.
Time complexity: O(n log n) (due to sorting)
Space complexity: O(n) (for map and key list)

package main

import (
    "fmt"
    "sort"
)

func main() {
    result := longestConsecutive([]int{-2, 3, 7, 2, 5, 4, 6, -1, 1})
    fmt.Println(result)
}

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    lookup := make(map[int]struct{})
    for _, item := range nums {
        lookup[item] = struct{}{}
    }

    keys := make([]int, 0, len(lookup))
    for key := range lookup {
        keys = append(keys, key)
    }

    sort.Ints(keys)

    local, global := 1, 1

    for i := 1; i < len(keys); i++ {
        if keys[i] == keys[i-1]+1 {
            local++
        } else {
            if local > global {
                global = local
            }
            local = 1
        }
    }

    if global < local {
        return local
    }
    return global
}