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)

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)

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)

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

Leetcode: link