Leetcode 217 - Contains Duplicate

easy

Question

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 <= 105
• -109 <= nums[i] <= 109

---

Solution

The main trick to this is to store elements we've seen, then check if it has previously been seen. For this implementation a lookup needs to be done. We can perform lookup on hashmaps with O(1), so we use a hashmap, hashset or set to store previously seen elements for quick lookups.

from typing import List

def containsDuplicate(nums: List[int]) -> bool:
    # set to store previously seen elements
    nums_set = set()
    for num in nums:
        # if we've come across this value return
        if num in nums_set:
            return True
        # else add it to the set
        nums_set.add(num)
    # if we've gone through the list and see nothing, return `False`
    return False