Contains Duplicate

Problem

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

Approach: Hash Set

The key insight is to use a hash set to track numbers we’ve already seen. As we iterate through the array, we check if the current number exists in the set. If it does, we’ve found a duplicate. If not, we add it to the set and continue.

Implementation

class 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

Alternative (More Pythonic):

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

Complexity Analysis

Time Complexity: O(n), where n is the length of the array. We iterate through the array once, and set operations (add and lookup) are O(1) on average.
Space Complexity: O(n) in the worst case, where all elements are unique and we store all of them in the set.

Key Insights

Hash Set for O(1) Lookups: Using a set gives us constant-time lookups to check if we’ve seen a number before.
Early Return: We can return True as soon as we find a duplicate, avoiding unnecessary iterations.
Alternative Approach: The one-liner len(nums) != len(set(nums)) is elegant but requires processing the entire array before comparing lengths.
Why Not Sorting? Sorting the array first and checking adjacent elements would work but takes O(n log n) time, which is slower than the hash set approach.