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

Last updated

Was this helpful?