128. Longest Consecutive Sequence #

Problem #

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Problem Summary #

Given an unsorted array of integers, find the length of the longest consecutive sequence. The algorithm is required to have a time complexity of O(n).

Solution Ideas #

Given an array, find the longest consecutive sequence and output this maximum length. The required time complexity is O(n).
This problem can first be solved with brute force; see Solution 3 for the code. The idea is to store every number in a map, first deleting from the map any number nums[i] that has neither a previous number nums[i]-1 nor a next number nums[i]+1; such numbers are not consecutive on either side. Then find in the map a number whose previous number nums[i]-1 does not exist but whose next number nums[i]+1 does exist. Such a number is the starting point of a consecutive sequence, so keep searching forward until the sequence “breaks”. Finally, output the length of the longest sequence.
The optimal solution for this problem is Solution 1. For each number n that does not exist in the map, do 2 things when inserting it. First, check whether n - 1 and n + 1 both exist in the map. If they do, it means consecutive sequences exist, so update the left and right boundaries. Then the length of this small consecutive subsequence corresponding to n is sum = left + right + 1. The second thing is to update the corresponding length = sum at the left and right boundaries left and right.
This problem can also be solved with Union-Find; see Solution 2. Use each number’s index in nums, and perform union() between indices. Specifically, check whether the previous number nums[i]-1 and the next number nums[i]+1 exist in the map; if they do, perform union(). Finally, output the total number of elements in the set containing the most elements in the entire Union-Find.

Code #


package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

// Solution 1: map, time complexity O(n)
func longestConsecutive(nums []int) int {
	res, numMap := 0, map[int]int{}
	for _, num := range nums {
		if numMap[num] == 0 {
			left, right, sum := 0, 0, 0
			if numMap[num-1] > 0 {
				left = numMap[num-1]
			} else {
				left = 0
			}
			if numMap[num+1] > 0 {
				right = numMap[num+1]
			} else {
				right = 0
			}
			// sum: length of the sequence n is in
			sum = left + right + 1
			numMap[num] = sum
			// keep track of the max length
			res = max(res, sum)
			// extend the length to the boundary(s) of the sequence
			// will do nothing if n has no neighbors
			numMap[num-left] = sum
			numMap[num+right] = sum
		} else {
			continue
		}
	}
	return res
}

// Solution 2: Union-Find
func longestConsecutive1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numMap, countMap, lcs, uf := map[int]int{}, map[int]int{}, 0, template.UnionFind{}
	uf.Init(len(nums))
	for i := 0; i < len(nums); i++ {
		countMap[i] = 1
	}
	for i := 0; i < len(nums); i++ {
		if _, ok := numMap[nums[i]]; ok {
			continue
		}
		numMap[nums[i]] = i
		if _, ok := numMap[nums[i]+1]; ok {
			uf.Union(i, numMap[nums[i]+1])
		}
		if _, ok := numMap[nums[i]-1]; ok {
			uf.Union(i, numMap[nums[i]-1])
		}
	}
	for key := range countMap {
		parent := uf.Find(key)
		if parent != key {
			countMap[parent]++
		}
		if countMap[parent] > lcs {
			lcs = countMap[parent]
		}
	}
	return lcs
}

// Solution 3: brute force, time complexity O(n^2)
func longestConsecutive2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numMap, length, tmp, lcs := map[int]bool{}, 0, 0, 0
	for i := 0; i < len(nums); i++ {
		numMap[nums[i]] = true
	}
	for key := range numMap {
		if !numMap[key-1] && !numMap[key+1] {
			delete(numMap, key)
		}
	}
	if len(numMap) == 0 {
		return 1
	}
	for key := range numMap {
		if !numMap[key-1] && numMap[key+1] {
			length, tmp = 1, key+1
			for numMap[tmp] {
				length++
				tmp++
			}
			lcs = max(lcs, length)
		}
	}
	return max(lcs, length)
}