Longest Consecutive Sequence

Medium

The problem

Given an unsorted list of numbers, return the length of the longest run of numbers that follow each other with no gaps, like 4, 5, 6, 7. The numbers can be anywhere in the list, in any order.

Example 1
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
The longest run is 1, 2, 3, 4, which has length 4.
Example 2
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Every number from 0 to 8 is present, so the run 0, 1, ..., 8 has length 9.
Example 3
Input: nums = []
Output: 0
An empty list has no runs.

Limits

0 ≤ nums.length ≤ 100,000
-1,000,000,000 ≤ nums[i] ≤ 1,000,000,000
The list may contain repeated numbers

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Sorting costs O(n log n). Which numbers are the only ones worth starting a run from?

The idea

Put all numbers in a set. Only start counting at a number whose predecessor (x−1) is NOT in the set, then walk x+1, x+2… while present.

Target: O(n) time, O(n) space

Go function shape

func longestConsecutive(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LongestConsecutive: only start counting at the beginning of a run (x-1 is absent), so every number is
// visited a constant number of times and the whole thing is O(n).
func LongestConsecutive(nums []int) int {
	set := make(map[int]bool, len(nums))
	for _, n := range nums {
		set[n] = true
	}
	best := 0
	for n := range set {
		if set[n-1] {
			continue // not the start of a run
		}
		length := 1
		for set[n+length] {
			length++
		}
		best = max(best, length)
	}
	return best
}

Read the lesson: Arrays & Hash Map