The Contains Duplicate problem is a common algorithmic challenge that involves determining whether a given array of integers contains any duplicate elements. This problem is fundamental for understanding array manipulation and hash-based data structures.

In this post, we will explore multiple ways to solve this problem in Go (Golang), starting with a brute-force approach, then an optimized sorting-based approach, and concluding with the most efficient solution using a map (Go's equivalent of a hash table).

Problem Definition

You are given an array of integers nums. Your task is to determine if any value appears at least twice in the array. Return true if any value appears more than once, otherwise return false.

Example:

Input: nums = [1, 2, 3, 1]
Output: true

Input: nums = [1, 2, 3, 4]
Output: false

Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true

Constraints:

  • The length of the array can be up to (10^5) elements.
  • Each element in the array can range from (-10^9) to (10^9).

Let’s explore three different ways to solve this problem using Go.

Solution 1: Brute-Force Approach

Approach:

The brute-force approach involves comparing every element in the array with every other element. If any two elements are equal, we return true. If no duplicates are found after all comparisons, we return false.

Code Implementation:

package main

import "fmt"

func containsDuplicate(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] {
                return true  // Duplicate found
            }
        }
    }
    return false  // No duplicates found
}

func main() {
    nums := []int{1, 2, 3, 1}
    fmt.Println(containsDuplicate(nums))  // Output: true
}

Time and Space Complexity:

  • Time Complexity: O(n²) due to the two nested loops.
  • Space Complexity: O(1), since no extra space is used, except for the variables needed.

Explanation:

In this brute-force solution, we use two loops: the outer loop picks an element, and the inner loop compares it to all subsequent elements in the array. If two elements are found to be the same, the function returns true. If no duplicates are found, the function returns false.

Drawbacks:

This solution is inefficient for large arrays, as its O(n²) time complexity makes it impractical for arrays with thousands or millions of elements.

Solution 2: Sorting Approach

Approach:

A more efficient solution involves sorting the array first. Once sorted, any duplicate elements will be adjacent to each other. After sorting, we only need to check whether any two consecutive elements are the same.

Code Implementation:

package main

import (
    "fmt"
    "sort"
)

func containsDuplicate(nums []int) bool {
    sort.Ints(nums)  // Sort the array
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {  // Compare adjacent elements
            return true
        }
    }
    return false  // No duplicates found
}

func main() {
    nums := []int{1, 2, 3, 1}
    fmt.Println(containsDuplicate(nums))  // Output: true
}

Time and Space Complexity:

  • Time Complexity: O(n log n) due to the sorting operation.
  • Space Complexity: O(1) if the sorting is done in place using sort.Ints().

Explanation:

This solution sorts the array using Go’s sort.Ints() function, which has a time complexity of O(n log n). After sorting, we iterate through the array and check if any two consecutive elements are the same. If they are, we return true. If no duplicates are found, the function returns false.

Benefits and Drawbacks:

  • Benefits: This solution is more efficient than the brute-force method, as sorting reduces the number of comparisons.
  • Drawbacks: Sorting modifies the original array, and it still has a time complexity of O(n log n), which is not optimal for very large arrays.

Solution 3: Using a Map (Optimal Solution)

Approach:

The most efficient way to solve this problem is by using a map in Go, which acts like a hash table. We can iterate through the array and check if an element already exists in the map. If it does, we return true. If not, we add the element to the map and continue.

Code Implementation:

package main

import "fmt"

func containsDuplicate(nums []int) bool {
    seen := make(map[int]bool)  // Create a map to store unique elements
    for _, num := range nums {
        if seen[num] {  // If the element is already in the map
            return true  // Duplicate found
        }
        seen[num] = true  // Add the element to the map
    }
    return false  // No duplicates found
}

func main() {
    nums := []int{1, 2, 3, 1}
    fmt.Println(containsDuplicate(nums))  // Output: true
}

Time and Space Complexity:

  • Time Complexity: O(n) because we iterate through the array once, and map operations (insertions and lookups) take O(1) on average.
  • Space Complexity: O(n) due to the extra space used by the map to store the elements.

Explanation:

This approach leverages a map to store the unique elements in the array. As we loop through the array, we check if the current element is already in the map. If it is, we return true because a duplicate has been found. Otherwise, we add the element to the map. If no duplicates are found after the loop completes, we return false.

Benefits and Drawbacks:

  • Benefits: This is the most efficient solution with O(n) time complexity, and it does not modify the original array.
  • Drawbacks: The extra memory required for the map makes the space complexity O(n), but this is usually an acceptable trade-off for the performance benefits.

Edge Cases

When solving the Contains Duplicate problem, it is essential to consider different edge cases to ensure that the solution works in various scenarios. Below are some edge cases that you should account for in your implementation:

1. Empty Array:

If the input array is empty, there are no elements to compare, so the function should return false.

Example:

nums := []int{}
fmt.Println(containsDuplicate(nums))  // Output: false
  • Expected Output: Since there are no elements in the array, there cannot be any duplicates, so the output should be false.

2. Array with One Element:

If the input array contains only one element, it is impossible to have duplicates, so the function should return false.

Example:

nums := []int{1}
fmt.Println(containsDuplicate(nums))  // Output: false
  • Expected Output: Since there is only one element, it cannot have any duplicates, so the output should be false.

3. Array with All Unique Elements:

If the input array consists of unique elements (i.e., no duplicates), the function should return false.

Example:

nums := []int{1, 2, 3, 4, 5}
fmt.Println(containsDuplicate(nums))  // Output: false
  • Expected Output: All elements in the array are unique, so the output should be false.

4. Array with All Duplicate Elements:

If the entire array consists of the same element repeated multiple times, the function should return true.

Example:

nums := []int{1, 1, 1, 1, 1}
fmt.Println(containsDuplicate(nums))  // Output: true
  • Expected Output: Since every element in the array is the same, the function should return true.

5. Array with Large Numbers:

The array may contain very large or very small integer values within the range [-10^9, 10^9]. Ensure the solution handles large inputs correctly.

Example:

nums := []int{-1000000000, 1000000000}
fmt.Println(containsDuplicate(nums))  // Output: false
  • Expected Output: Since the two elements are different and within the given range, the function should return false.

6. Array with Negative and Positive Numbers:

The array can contain both negative and positive numbers. Ensure the function correctly handles and differentiates between them.

Example:

nums := []int{-1, 2, -3, 4, -1}
fmt.Println(containsDuplicate(nums))  // Output: true
  • Expected Output: The element -1 appears twice in the array, so the function should return true.

7. Array with Zeros:

The array may contain zeros, and the solution should handle duplicates of zero correctly.

Example:

nums := []int{0, 1, 2, 3, 0}
fmt.Println(containsDuplicate(nums))  // Output: true
  • Expected Output: Since 0 appears twice in the array, the function should return true.

8. Array with Mixed Duplicates and Unique Elements:

The array may contain a mix of duplicate and unique elements, so the function should return true as soon as a duplicate is found.

Example:

nums := []int{1, 2, 3, 2, 5}
fmt.Println(containsDuplicate(nums))  // Output: true
  • Expected Output: The element 2 appears twice, so the function should return true.

Conclusion

In this post, we explored three different ways to solve the Contains Duplicate problem in Go:

  1. Brute-force approach: Simple but inefficient, with O(n²) time complexity.
  2. Sorting approach: More efficient with O(n log n) time complexity, but modifies the original array.
  3. Map-based approach: The optimal solution with O(n) time complexity and O(n) space complexity, making it the best choice for large datasets.

In most cases, the map-based solution is the most practical due to its efficiency and ease of implementation.