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)
}