> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/217.-contains-duplicate.md).

# 217. Contains Duplicate

🟩 Easy

Given an integer array `nums`, return `true` if any value appears at least twice in the array, and return `false` if every element is distinct.

## Example 1

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

## Example 2

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

## Example 3

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

## Constraints

* `1 <= nums.length <= 10^5`
* `-10^9 <= nums[i] <= 10^9`

## Solution

My Solution (Hash Map)

```go
func containsDuplicate(nums []int) bool {
    if len(nums) < 2 {
        return false
    }

    m := make(map[int]bool)

    for _, num := range nums {
        if _, ok := m[num]; ok {
            return true
        }
        m[num]=true
    }

    return false
}
```

Optimal Solution 1 (Memory-Efficient Set)

```go
func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{})
    
    for _, num := range nums {
        if _, exists := seen[num]; exists {
            return true
        }
        seen[num] = struct{}{}
    }
    
    return false
}
```

Optimal Solution 2 (Sorting)

```go
func containsDuplicate(nums []int) bool {
    sort.Ints(nums)
    
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            return true
        }
    }
    
    return false
}
```

### Approach Analysis

This problem demonstrates multiple efficient approaches:

1. Hash Map (Your Solution):
   * Track seen numbers with bool values
   * Early termination on finding duplicate
   * Simple and effective approach
   * Good balance of time and space
2. Memory-Efficient Set:
   * Uses empty struct instead of bool
   * Same logic as hash map
   * More memory efficient
   * Idiomatic Go solution
3. Sorting Approach:
   * Trade time for space
   * No extra memory needed
   * Simple adjacent comparison
   * Modifies input array

### Visualization of Both Approaches

#### Hash Map Process (Your Solution)

```
Input: [1,2,3,1]

Step 1: map = {}
Step 2: map = {1: true}
Step 3: map = {1: true, 2: true}
Step 4: map = {1: true, 2: true, 3: true}
Step 5: Check 1 → found in map → return true
```

#### Memory-Efficient Set Process

```
Input: [1,2,3,1]

Step 1: set = {}
Step 2: set = {1: struct{}{}}
Step 3: set = {1: struct{}{}, 2: struct{}{}}
Step 4: set = {1: struct{}{}, 2: struct{}{}, 3: struct{}{}}
Step 5: Check 1 → exists → return true
```

#### Sorting Process

```
Input: [1,2,3,1]

Step 1: Sort → [1,1,2,3]
Step 2: Compare adjacent:
1 == 1 → return true
```

### Complexity Analysis

#### Hash Map Solution (Your Solution)

* Time: O(n)
  * Single pass through array
  * O(1) map operations
  * Early termination possible
* Space: O(n)
  * Stores all unique elements
  * Uses bool values
  * Worst case: all unique

#### Memory-Efficient Set

* Time: O(n)
  * Same as hash map
  * O(1) set operations
  * Early termination
* Space: O(n)
  * Stores unique elements
  * Uses empty struct (0 bytes)
  * More memory efficient

#### Sorting Solution

* Time: O(n log n)
  * Dominated by sorting
  * Linear scan after sort
  * No early termination
* Space: O(1)
  * In-place sorting
  * No extra storage
  * Modifies input array

### Why Solutions Work

1. Hash Map Logic:
   * Each number seen once
   * Instant lookup
   * Returns on first duplicate
   * Simple hash table principle
2. Set Logic:
   * Set ensures uniqueness
   * Memory optimization
   * Same time complexity
   * More space efficient
3. Sorting Logic:
   * Duplicates become adjacent
   * One-pass comparison
   * Space-time tradeoff
   * Simple implementation

### When to Use

1. Hash Map/Set When:
   * Can't modify input
   * Memory available
   * Need early termination
   * Average case performance
2. Sorting When:
   * Memory constrained
   * Can modify input
   * Order useful later
   * Simplicity preferred

### Common Patterns & Applications

1. Related Problems:
   * Contains Duplicate II
   * Contains Duplicate III
   * Find All Duplicates
   * Find the Duplicate Number
2. Key Techniques:
   * Hash table usage
   * Set operations
   * In-place sorting
   * Space-time tradeoffs

### Interview Tips

1. Solution Highlights:
   * Discuss tradeoffs
   * Mention optimizations
   * Consider constraints
   * Handle edge cases
2. Common Pitfalls:
   * Unnecessary length checks
   * Not considering memory
   * Missing edge cases
   * Inefficient lookups
3. Testing Strategy:
   * Empty array
   * Single element
   * All duplicates
   * No duplicates
   * Large arrays
4. Follow-up Questions:
   * Memory constraints?
   * Maintain order?
   * Stream processing?
   * Parallel solution?

![result](/files/yn5zuLbMvEPdTgLdIn7B)

Leetcode: [link](https://leetcode.com/problems/contains-duplicate/description/)