🟩 Contains Duplicate (#217)

🔗 Problem Link

• Leetcode 217: Contains Duplicate
• Neetcode: Duplicate Integer

📋 Problem Statement

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

💡 Examples

Example 1

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

Example 2

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

🔑 Key Insights & Approach

Core Observation: If we've seen a number before while iterating through the array, we immediately have a duplicate — no need to continue checking.

Why Hash Set/Table?

• Checking membership: O(1) average time
• Beats sorting O(n log n) or nested loops O(n²)

Two Solution Approaches:

1. Length comparison: len(nums) != len(set(nums)) - simple one-liner
2. Early exit: Track seen elements, return immediately on first duplicate - more efficient

This is the "Have we seen this before?" pattern:

• Useful for: duplicates, two sum, first repeated element
• Trade-off: O(n) extra space for O(n) time

🐍 Solution: Python

Approach 1: Using Set

Time Complexity: O(n) | Space Complexity: O(n)

def contains_duplicate(nums):
    return len(nums) != len(set(nums))

Approach 2: Using Hash Table

Time Complexity: O(n) | Space Complexity: O(n)

def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

🔵 Solution: Golang

Approach 1: Using Map/Set

Time Complexity: O(n) | Space Complexity: O(n)

func containsDuplicate(nums []int) bool {
    hashTable := make(map[int]bool)
    for _, num := range nums {
        if _, ok := hashTable[num]; ok {
            return true
        }
        hashTable[num] = true
    }
    return false
}

📚 References

• YouTube: Contains Duplicate - Leetcode 217 - Python