Longest Consecutive Sequence

1. Problem Description

Given an unsorted integer array nums, find the length of the longest sequence of consecutive numbers. The elements do not need to be contiguous in the original array.

2. Approach

1. Approach 1
   • Sort first
   • Traverse the array and count adjacent elements whose difference is 1
2. Approach 2
   • Traverse once and place all values into a set
   • Traverse again and check whether n-1 exists in the set

3. Implementation

3.1. Sort

import "sort"

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

	sort.Ints(nums)

	maxCount := 1
	count := 1
	for i := 0; i < len(nums)-1; i++ {
		diff := nums[i+1] - nums[i]
		if diff <= 1 {
			count += diff
		} else {
			count = 1
		}
		maxCount = max(count, maxCount)
	}

	return maxCount
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

3.2. map

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

	m := make(map[int]bool, 0)
	for _, num := range nums {
		m[num] = true
	}

	maxCount := 0
	for num := range m {
		// Deduplicate by counting only from the smallest number in each sequence
		if m[num-1] {
			continue
		}

		currentCount := 1
		currentNum := num
		for m[currentNum+1] {
			currentNum++
			currentCount++
		}
		maxCount = Max(currentCount, maxCount)
	}

	return maxCount
}

4. References

• Longest Consecutive Sequence - LeetCode
• Longest Increasing Subsequence