Introduction to the Contains Duplicate Problem
The "Contains Duplicate" problem is one of the most fundamental algorithmic challenges you'll encounter in coding interviews and competitive programming. The premise is deceptively simple: given an array of integers, determine whether any value appears at least twice. Despite its simplicity, this problem serves as an excellent gateway into understanding time and space complexity trade-offs, hash-based data structures, and idiomatic Go programming.
In this tutorial, we'll explore multiple approaches to solving this problem in Go, starting from the naive brute-force method and progressing to the optimal hash map solution. Along the way, you'll learn about Go's built-in data structures, performance benchmarking, and best practices for writing clean, efficient code.
What Is the Contains Duplicate Problem?
Formally, the problem can be stated as follows: Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.
For example, given the input [1, 2, 3, 1], the function should return true because the value 1 appears twice. Conversely, given [1, 2, 3, 4], the function should return false because all elements are unique.
This problem is listed as LeetCode 217 and is frequently used by interviewers to assess a candidate's understanding of basic data structures and algorithmic complexity. While the problem itself is straightforward, the way you approach it reveals a great deal about your problem-solving instincts.
Why It Matters
You might wonder why such a simple problem deserves a dedicated tutorial. The answer lies in what the problem teaches. First, it introduces the concept of time complexity trade-offs. A naive solution might be easy to write but perform poorly on large inputs, while an optimized solution requires a deeper understanding of data structures.
Second, the problem demonstrates the power of hash-based lookups, which achieve average O(1) time complexity. This concept underpins countless real-world applications, from database indexing to caching systems to deduplication pipelines.
Finally, in a Go-specific context, this problem provides an opportunity to practice working with slices, maps, and the language's unique approach to memory and performance. Mastering these fundamentals will pay dividends as you tackle more complex challenges.
Setting Up Your Go Environment
Before diving into the code, ensure you have Go installed. You can verify your installation by running the following command in your terminal:
go version
If Go is not installed, download it from the official Go website and follow the installation instructions for your operating system. Once installed, create a new directory for this tutorial and initialize a Go module:
mkdir contains-duplicate
cd contains-duplicate
go mod init containsduplicate
Now create a file named main.go where we'll write and test our solutions.
Approach 1: Brute Force
The most intuitive approach is to compare every pair of elements in the array. For each element, check it against every other element to see if a duplicate exists. This is the brute-force method.
Implementation
package main
import "fmt"
func containsDuplicateBruteForce(nums []int) bool {
n := len(nums)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if nums[i] == nums[j] {
return true
}
}
}
return false
}
func main() {
nums := []int{1, 2, 3, 1}
fmt.Println(containsDuplicateBruteForce(nums)) // Output: true
}
Analysis
The brute-force approach has a time complexity of O(n²) because, in the worst case, we compare every element with every other element. The space complexity is O(1) since we only use a constant amount of extra memory.
While this solution works for small inputs, it becomes prohibitively slow for large arrays. For example, an array with 100,000 elements would require roughly 5 billion comparisons in the worst case. Clearly, we need a better approach.
Approach 2: Sorting First
A more efficient approach involves sorting the array first. Once sorted, any duplicate values will be adjacent to each other. We can then make a single pass through the array, comparing each element with its neighbor.
Implementation
package main
import (
"fmt"
"sort"
)
func containsDuplicateSort(nums []int) bool {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return true
}
}
return false
}
func main() {
nums := []int{1, 2, 3, 4, 2}
fmt.Println(containsDuplicateSort(nums)) // Output: true
}
Analysis
Sorting the array takes O(n log n) time, and the subsequent linear scan takes O(n) time. The overall time complexity is therefore O(n log n), which is a significant improvement over the brute-force approach. The space complexity depends on the sorting algorithm used by Go's standard library; in most cases, it operates in O(log n) space due to the recursive calls in quicksort.
This approach is a good middle ground. It's efficient enough for most practical purposes and doesn't require additional data structures. However, it modifies the original array, which may be undesirable in some scenarios. If you need to preserve the original order, you'd have to create a copy first, increasing the space complexity to O(n).
Approach 3: Hash Map (Optimal Solution)
The optimal solution uses a hash map to track which elements we've already seen. As we iterate through the array, we check if the current element exists in the map. If it does, we've found a duplicate and can return true immediately. If not, we add the element to the map and continue.
Implementation
package main
import "fmt"
func containsDuplicate(nums []int) bool {
seen := make(map[int]bool)
for _, num := range nums {
if seen[num] {
return true
}
seen[num] = true
}
return false
}
func main() {
testCases := [][]int{
{1, 2, 3, 1},
{1, 2, 3, 4},
{1, 1, 1, 3, 3, 4, 3, 2, 4, 2},
{},
{42},
}
for _, tc := range testCases {
fmt.Printf("Input: %v -> Output: %v\n", tc, containsDuplicate(tc))
}
}
Expected output:
Input: [1 2 3 1] -> Output: true
Input: [1 2 3 4] -> Output: false
Input: [1 1 1 3 3 4 3 2 4 2] -> Output: true
Input: [] -> Output: false
Input: [42] -> Output: false
Analysis
The hash map approach achieves O(n) time complexity because each lookup and insertion into a Go map is, on average, an O(1) operation. We make a single pass through the array, performing at most one lookup and one insertion per element.
The trade-off is space complexity: in the worst case (when all elements are unique), we store every element in the map, resulting in O(n) space usage. For most practical scenarios, this is an acceptable trade-off given the dramatic improvement in time complexity.
This is the solution most interviewers expect, and it's the one you should reach for in production code unless you have specific constraints that make the space usage problematic.
Approach 4: Using a Set Abstraction
While Go doesn't have a built-in set type, we can create a simple set abstraction using a map with empty struct values. Empty structs consume zero bytes of memory, making them ideal for this purpose.
Implementation
package main
import "fmt"
type IntSet struct {
items map[int]struct{}
}
func NewIntSet() *IntSet {
return &IntSet{items: make(map[int]struct{})}
}
func (s *IntSet) Add(val int) {
s.items[val] = struct{}{}
}
func (s *IntSet) Contains(val int) bool {
_, ok := s.items[val]
return ok
}
func containsDuplicateSet(nums []int) bool {
set := NewIntSet()
for _, num := range nums {
if set.Contains(num) {
return true
}
set.Add(num)
}
return false
}
func main() {
nums := []int{10, 20, 30, 10}
fmt.Println(containsDuplicateSet(nums)) // Output: true
}
This approach is functionally identical to the hash map solution but provides a cleaner, more reusable abstraction. If your codebase frequently needs set operations, investing in a set type can improve readability and maintainability.
Benchmarking the Solutions
To truly understand the performance differences between these approaches, let's write benchmarks. Create a file named contains_duplicate_test.go with the following content:
package main
import (
"math/rand"
"testing"
)
func generateLargeSlice(n int) []int {
nums := make([]int, n)
for i := 0; i < n; i++ {
nums[i] = rand.Intn(n)
}
return nums
}
func BenchmarkBruteForce(b *testing.B) {
nums := generateLargeSlice(1000)
b.ResetTimer()
for i := 0; i < b.N; i++ {
containsDuplicateBruteForce(nums)
}
}
func BenchmarkSort(b *testing.B) {
nums := generateLargeSlice(10000)
b.ResetTimer()
for i := 0; i < b.N; i++ {
containsDuplicateSort(nums)
}
}
func BenchmarkHashMap(b *testing.B) {
nums := generateLargeSlice(10000)
b.ResetTimer()
for i := 0; i < b.N; i++ {
containsDuplicate(nums)
}
}
Run the benchmarks with the following command:
go test -bench=. -benchmem
You'll observe that the hash map solution significantly outperforms the brute-force approach and is competitive with the sorting approach, especially as input sizes grow. The brute-force benchmark uses a smaller slice (1,000 elements) because it would be too slow with larger inputs.
Edge Cases to Consider
When implementing this solution, it's important to handle edge cases correctly. Here are the scenarios you should test:
- Empty array: An empty array has no duplicates, so the function should return
false. - Single element: An array with one element cannot have duplicates, so the function should return
false. - All duplicates: An array where every element is the same should return
true. - Negative numbers: The solution should work correctly with negative integers.
- Large numbers: Ensure the solution handles large integer values without overflow issues.
- Adjacent duplicates: Duplicates that appear next to each other should be detected efficiently.
- Duplicates at the end: The worst case for early termination is when duplicates appear at the very end of the array.
Here's a comprehensive test suite that covers these cases:
package main
import "testing"
func TestContainsDuplicate(t *testing.T) {
tests := []struct {
name string
nums []int
want bool
}{
{"empty array", []int{}, false},
{"single element", []int{1}, false},
{"no duplicates", []int{1, 2, 3, 4, 5}, false},
{"has duplicates", []int{1, 2, 3, 1}, true},
{"all same", []int{7, 7, 7, 7}, true},
{"negatives", []int{-1, -2, -3, -1}, true},
{"large numbers", []int{2147483647, -2147483648, 2147483647}, true},
{"duplicates at end", []int{1, 2, 3, 4, 5, 3}, true},
{"two elements same", []int{1, 1}, true},
{"two elements diff", []int{1, 2}, false},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got := containsDuplicate(tt.nums)
if got != tt.want {
t.Errorf("containsDuplicate(%v) = %v, want %v", tt.nums, got, tt.want)
}
})
}
}
Run the tests with:
go test -v
Best Practices
Now that we've covered the implementations, let's discuss some best practices to keep in mind when solving this and similar problems in Go.
Pre-allocate Maps When Possible
If you know the approximate size of the input, you can pre-allocate the map to avoid rehashing during insertion. Go's make function accepts a size hint as the second argument:
seen := make(map[int]bool, len(nums))
This doesn't strictly set the map's size, but it provides a hint that helps the runtime allocate an appropriately sized hash table, reducing the number of rehash operations.
Use Early Termination
Notice that all our solutions return true as soon as a duplicate is found. This is a form of early termination, and it can dramatically improve performance when duplicates appear early in the array. Always look for opportunities to short-circuit unnecessary work.
Choose the Right Data Structure
The hash map is the optimal choice for this problem, but different problems may call for different structures. For example, if you needed to find duplicates in a sorted stream of data, a single comparison with the previous element would suffice. Always analyze the specific constraints of your problem before choosing a data structure.
Avoid Mutating Input
The sorting approach modifies the original array, which can lead to subtle bugs if the caller doesn't expect it. If you need to preserve the original data, create a copy before sorting:
func containsDuplicateSortSafe(nums []int) bool {
copySlice := make([]int, len(nums))
copy(copySlice, nums)
sort.Ints(copySlice)
for i := 1; i < len(copySlice); i++ {
if copySlice[i] == copySlice[i-1] {
return true
}
}
return false
}
Write Table-Driven Tests
Go's testing framework is well-suited for table-driven tests, as demonstrated in the test suite above. This pattern makes it easy to add new test cases and clearly documents the expected behavior for each input. Always include edge cases in your test tables.
Consider Memory Constraints
If memory is a concern—for example, when working with extremely large datasets that don't fit in RAM—the hash map approach may not be feasible. In such cases, an external sorting approach or a probabilistic data structure like a Bloom filter might be more appropriate. Understanding these trade-offs is essential for building robust, scalable systems.
Variations of the Problem
The Contains Duplicate problem has several interesting variations that build on the same foundational concepts. Being familiar with these variations will deepen your understanding and prepare you for related interview questions.
Contains Duplicate II
In this variation, you must determine whether there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k. The solution uses a hash map that stores the most recent index of each element:
func containsNearbyDuplicate(nums []int, k int) bool {
indexMap := make(map[int]int)
for i, num := range nums {
if prevIndex, ok := indexMap[num]; ok && i-prevIndex <= k {
return true
}
indexMap[num] = i
}
return false
}
Contains Duplicate III
This variation adds a value constraint: find indices i and j such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k. This is significantly more complex and typically requires a balanced BST or bucket-based approach for an efficient solution.
Conclusion
The Contains Duplicate problem, while simple on the surface, offers valuable lessons in algorithmic thinking and Go programming. We explored four approaches—brute force, sorting, hash map, and a set abstraction—each with its own trade-offs in terms of time and space complexity. The hash map solution stands out as the optimal approach for most scenarios, delivering O(n) time complexity with O(n) space usage. By understanding these trade-offs, writing comprehensive tests, and following Go best practices like pre-allocation and early termination, you'll be well-equipped to tackle not only this problem but also the countless variations and related challenges you'll encounter in your development career. Remember that the journey from a naive solution to an optimal one is where the real learning happens, so don't skip the brute-force step—it builds the intuition you need to recognize when and how to optimize.