Contains Duplicate

Problem Statement

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. The array nums contains duplicate values.

Example 1:

To determine whether the array nums contains duplicate values, you can implement a solution that checks for repeated elements.

Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs twice.

Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs twice.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.

Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct.

Example 3:

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

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

Approach

Initial Thoughts

This is a classic problem that tests your understanding of data structures and their time complexities. The naive approach would be to compare every element with every other element (O(n²)), but we can do much better using a hash set.

Strategy

Use a hash set to track elements we’ve already seen. As we iterate through the array, check if the current element exists in the set. If it does, we’ve found a duplicate. If not, add it to the set and continue.

Key Insights

• Hash set provides O(1) average-case lookup time
• We can return true immediately upon finding the first duplicate (early exit)
• No need to count occurrences – just detect if something appears more than once
• Space-time tradeoff: we use O(n) space to achieve O(n) time
• Alternative: sort first, then check adjacent elements (O(n log n) time, O(1) space)

Algorithm Steps

1. Create an empty hash set seen
2. Iterate through each element num in nums:
   • Check if num is already in seen
   • If yes, return true (duplicate found)
   • If no, add num to seen
3. If loop completes without finding duplicates, return false

Complexity Analysis

Time Complexity: O(n) – Single pass through the array, where n is the length of nums. Hash set operations (add/lookup) are O(1) average case.

Space Complexity: O(n) – In worst case (all elements unique), we store all n elements in the hash set.

Code

def containsDuplicate(nums):
    seen = set()  # Hash set to track elements we've encountered</em>
    
    for num in nums:
        if num in seen:
            return True  # Found a duplicate</em>
        seen.add(num)
    
    return False  # No duplicates found</em>

def containsDuplicate(nums):
    seen = set()  # Hash set to track elements we've encountered</em>
    
    for num in nums:
        if num in seen:
            return True  # Found a duplicate</em>
        seen.add(num)
    
    return False  # No duplicates found</em>

Alternative Approach (One-liner):

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

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

This compares the length of the original array with the length of its set representation. If they differ, duplicates exist.

Code Walkthrough

Line 2: Initialize empty set seen to track unique elements we’ve encountered

Line 4: Loop through each element in the array

Line 5: Check if current element already exists in our set

• If yes, we’ve seen it before → duplicate found → return True

Line 6: Return True immediately (early exit optimization)

Line 7: Add current element to the set for future comparisons

Line 9: If we complete the entire loop without finding duplicates, return False

Edge Cases to Consider

1. Minimum size array: [1] → false (single element, no duplicates possible)
2. Two elements – duplicate: [1, 1] → true
3. Two elements – distinct: [1, 2] → false
4. All same elements: [5, 5, 5, 5] → true
5. Duplicate at start: [1, 1, 2, 3] → true (early exit)
6. Duplicate at end: [1, 2, 3, 3] → true
7. Large numbers: Handle values up to 10^9
8. Negative numbers: [-1, -1, 2] → true
9. Mix of positive and negative: [-1, 0, 1, -1] → true

Similar Problems

• LC 217: Contains Duplicate (this problem)
• LC 219: Contains Duplicate II (duplicates within k distance)
• LC 220: Contains Duplicate III (duplicates with value difference constraint)
• LC 136: Single Number
• LC 287: Find the Duplicate Number
• LC 442: Find All Duplicates in an Array
• LC 1: Two Sum (uses similar hash set technique)

Personal Notes

• This is one of the easiest problems in NeetCode 150 – great warm-up
• Perfect example of when to use a hash set vs hash map (we don’t need to store counts)
• The one-liner solution is elegant but less efficient in practice (creates entire set upfront)
• Interview tip: mention the sorting alternative to show you know multiple approaches
• Sorting approach: Sort array O(n log n), then check adjacent elements O(n)
  • Tradeoff: slower time but O(1) space (if sorting in-place)
• In real interviews, always clarify if you can modify the input array
• Hash set approach is generally preferred for optimal time complexity
• This problem teaches the fundamental pattern: “use hash set to detect duplicates”