# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/217.-contains-duplicate.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.