Contains Duplicate

Problem

https://leetcode.com/problems/contains-duplicate/

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

Explanation:

The element 1 occurs at the indices 0 and 3.

Example 2:

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

Constraints:

• 1 <= nums.length <= 10:sup:`5`

• -10:sup:`9`<= nums[i] <= 10:sup:`9`

Pattern

Array, Hash Table, Sorting

Approaches

Hash Set

Explanation

We can use a hash set to track the element seen so far. If we encounter an element that is already in the set, it is a duplicate and we return true. If we finish iterating through the array without finding any duplicates, we return false.

Code

def containsDuplicate(nums: list[int]) -> bool:
    """Return whether any value appears at least twice in ``nums``."""
    seen: set[int] = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

Test

>>> from contains_duplicate__hash_set import containsDuplicate
>>> containsDuplicate([1, 2, 3, 1])
True
>>> containsDuplicate([1, 2, 3, 4])
False
>>> containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])
True

Complexity

\(n\) is the number of elements in nums.

Measure	Complexity	Notes
Time	\(O(n)\)	one pass through the array
Auxiliary Space	\(O(n)\)	the hash set can contain up to the whole array

contains_duplicate__hash_set.containsDuplicate(nums: list[int]) → bool

Return whether any value appears at least twice in nums.