Problem

Link to the LeetCode 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

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

Required knowledge

Hash table

A hash table or hash map is a data structure storing key-value pairs. Its essence is a so-called hash function that given a key returns an address in the table where the corresponding value will be placed. Ideally, the hash function generates a unique hash for every different key but always generates the same hash for the same key. In Python, the dictionary and the set types are two examples of this data structure.

The good thing about using hash tables is that while you

make a sacrifice in space complexity: 𝒪(n),
you gain it back in time complexity: average search, insert and delete: 𝒪(1).

Solution

We create a set for storing the elements we have already seen. For every element in the list, we check if it is already in the set. If so, we have found a duplicate, so we return True. Otherwise, we add the element to the set and continue. Finally, after checking all the elements we return False because we didn't find a duplicate.

def containsDuplicate(self, nums: List[int]) -> bool:
    checkedNums = set()

    for n in nums:
        if n in checkedNums:
            return True
        checkedNums.add(n)

    return False

Space complexity

It's 𝒪(n), since we store every value in the set. (In the worst case.)

Time complexity

What we do is:

search in the set: 𝒪(1),
insert to the set: 𝒪(1)

n times (for every element). So it is 𝒪(n) * (𝒪(1) + 𝒪(1)) which is 𝒪(n).

LeetCode #217 - Contains Duplicate

NeetCode - Arrays & Hashing

Table of contents