NUHMAN.com

Introduction

LeetCode 128: Longest Consecutive Sequence is a problem that requires finding the length of the longest consecutive elements sequence in an unsorted array. The goal is to return the length of the longest sequence of consecutive integers in the array, where the sequence can appear in any order. The challenge lies in achieving an efficient solution in terms of time complexity.

Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. The algorithm should run in O(n) time complexity, where n is the number of elements in the array.

Example:

go

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

Note:

• You must solve the problem in O(n) time complexity.
• The elements in the sequence do not have to be adjacent in the original array.

Approach:

Optimal Solution Using HashSet

The problem can be solved efficiently by leveraging a HashSet (or map in Go). The idea is to:

1. Insert elements into a Set: By inserting all elements into a set, we ensure that each element is unique and can be accessed in constant time.
2. Traverse each number in the array: For each number, check if it is the start of a potential sequence by verifying that num-1 is not in the set.
3. Extend the sequence: If a number is the start of a sequence, incrementally check for the next consecutive numbers (num+1, num+2, etc.) and count the length of the sequence.
4. Track the longest sequence: Keep track of the maximum length found during the process.

This approach has a time complexity of O(n) because each element is processed at most twice (once when checking if it’s the start of a sequence, and once when extending the sequence).

Go Implementation

Solution Using HashSet

go

package main

import "fmt"

func longestConsecutive(nums []int) int {
	// Create a set (map) to store unique elements
	numSet := make(map[int]bool)
	for _, num := range nums {
		numSet[num] = true
	}

	maxLength := 0

	// Traverse through each number in the set
	for num := range numSet {
		// Check if num is the beginning of a sequence
		if !numSet[num-1] {
			// Count the length of the sequence starting from num
			currentNum := num
			currentLength := 1

			// Count consecutive numbers
			for numSet[currentNum+1] {
				currentNum++
				currentLength++
			}

			// Update the maximum length
			if currentLength > maxLength {
				maxLength = currentLength
			}
		}
	}

	return maxLength
}

func main() {
	// Test case
	nums := []int{100, 4, 200, 1, 3, 2}
	result := longestConsecutive(nums)
	fmt.Println(result) // Output: 4
}

Explanation:

1. Creating a Set: We first create a map (acting as a set) to store all elements from the input array. This ensures that we have O(1) access time for checking if an element exists in the set.
2. Iterating Through the Set: For each number in the set, we check if it is the start of a sequence by verifying if num-1 exists in the set. If it doesn’t, it’s the start of a sequence.
3. Finding the Sequence Length: Once a potential sequence is found, we incrementally check the consecutive numbers (num+1, num+2, ...) and count how long the sequence continues.
4. Updating the Maximum Length: During the traversal, we keep track of the longest sequence encountered.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n)

Time Complexity:

• O(n) because we iterate through the array once to build the set and then iterate over the set (which contains n elements) to find the longest consecutive sequence.

Space Complexity:

• O(n) for the space used to store the elements in the set. In the worst case, all elements are unique and need to be stored in the set.

Edge Cases

1. Edge Case: Empty Input

• Input: []
• Output: 0
• Explanation: There are no elements in the array, so the longest sequence length is 0.

1. Edge Case: Array with Only One Element

• Input: [1]
• Output: 1
• Explanation: A single element forms a sequence of length 1.

1. Edge Case: Array with Duplicates

• Input: [1, 2, 2, 3, 4]
• Output: 4
• Explanation: The sequence [1, 2, 3, 4] is the longest consecutive sequence, and duplicates are ignored.

1. Edge Case: No Consecutive Numbers

• Input: [10, 20, 30, 40]
• Output: 1
• Explanation: There are no consecutive numbers, so the longest sequence is 1.

Conclusion

LeetCode 128: Longest Consecutive Sequence is a problem that can be efficiently solved using a HashSet to track elements and find the longest consecutive sequence in linear time. This approach ensures that we achieve the desired time complexity of O(n), where n is the number of elements in the array. The space complexity is also O(n) due to the storage of elements in the set.