LeetCode 217: Contains Duplicate - All Solutions Explained

Problem Statement

The Contains Duplicate problem (LeetCode 217) is an easy-level array challenge where you need to determine if any value appears at least twice in an integer array.

Copy codeInput: nums = [1,2,3,1]
Output: true

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

Explanation of the Best Solution

This approach uses a hash set to track seen elements with O(1) lookups:

1. Initialize Empty Set: To store seen numbers
2. Iterate Through Array:
3. For each number, check if it exists in the set
4. If yes, return true (duplicate found)
5. If no, add to set
6. Final Check: If loop completes without finding duplicates, return false

Step-by-Step Example

For nums = [1,2,3,1]: 1. Set = {}, check 1 → not in set → add 2. Set = {1}, check 2 → not in set → add 3. Set = {1,2}, check 3 → not in set → add 4. Set = {1,2,3}, check 1 → found in set → return true

Python Code (Hash Set Solution)

Copy codeclass Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

# Test cases
print(Solution().containsDuplicate([1,2,3,1]))  # Output: True
print(Solution().containsDuplicate([1,2,3,4]))  # Output: False

Complexity

• Time Complexity: O(n) - Single pass through array
• Space Complexity: O(n) - Worst case stores all elements
• Optimizations: Early termination when duplicate found

Why It's the Best

• Optimal O(n) time complexity
• Simple and clean implementation
• Works for both positive and negative numbers
• Standard approach for duplicate detection

Solution 2: Sorting (Alternative Approach)

Explanation

This approach sorts the array first, then checks adjacent elements:

1. Sort Array: In ascending order
2. Check Adjacent Elements: If any two neighbors are equal, duplicates exist
3. Return Result: Based on neighbor comparison

Step-by-Step Example

For nums = [1,2,3,1]: 1. Sorted array: [1,1,2,3] 2. Compare 1 and 1 → equal → return true

Python Code (Sorting Solution)

Copy codeclass Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]:
                return True
        return False

# Test cases
print(Solution().containsDuplicate([1,2,3,1]))  # Output: True
print(Solution().containsDuplicate([1,2,3,4]))  # Output: False

Complexity

• Time Complexity: O(n log n) - Dominated by sorting
• Space Complexity: O(1) - In-place sort (assuming heapsort)
• Drawbacks: Slower than hash set for large n

Pros and Cons

• Pros: Constant space (if sorting in-place)
• Cons: Slower time complexity
• Best for: When memory is constrained and n is small

Solution 3: Brute Force (Naive Approach)

Explanation

The straightforward approach compares every pair of elements:

1. Nested Loops: Compare each element with all subsequent elements
2. Early Termination: Return true if any duplicate found
3. Final Check: Return false if no duplicates found

Python Code (Brute Force Solution)

Copy codeclass Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

# Test cases
print(Solution().containsDuplicate([1,2,3,1]))  # Output: True
print(Solution().containsDuplicate([1,2,3,4]))  # Output: False

Complexity

• Time Complexity: O(n²) - Quadratic comparisons
• Space Complexity: O(1) - No additional storage
• When to Use: Only for very small arrays (n < 100)

Edge Cases to Consider

• Empty array → return false
• Single element → return false
• All elements same → return true
• Large input with no duplicates → must handle efficiently
• Negative numbers → all solutions work correctly

Final Thoughts

• Hash Set: Best for most cases (optimal time complexity)
• Sorting: Good when memory is limited
• Brute Force: Only for understanding the problem
• Key Insight: Tradeoffs between time and space complexity

For further practice, try similar problems like Contains Duplicate II (LeetCode 219) or Single Number (LeetCode 136).