Longest Consecutive Sequence

LeetCode 128 · View on LeetCode

Build a set from the array. Only start counting from sequence starts (numbers where n-1 is not in the set). Each number is visited at most twice, so it's O(n).

package main

import "fmt"

func longestConsecutive(nums []int) int {
	set := make(map[int]bool)
	for _, n := range nums {
		set[n] = true
	}
	best := 0
	for n := range set {
		if set[n-1] {
			continue // not a sequence start
		}
		length := 1
		for set[n+length] {
			length++
		}
		if length > best {
			best = length
		}
	}
	return best
}

func main() {
	fmt.Println(longestConsecutive([]int{100, 4, 200, 1, 3, 2})) // 4
	fmt.Println(longestConsecutive([]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1})) // 9
}