## DEV Community

Eda

Posted on • Originally published at rivea0.github.io

# LeetCode Meditations: 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.

For example:

[1, 2, 3, 1] // true
[1, 2, 3, 4] // false
[1, 1, 1, 3, 3, 4, 3, 2, 4, 2] // true


We can use a Set which only keeps the values without duplicates.

For each example, it would look like this:

new Set([1, 2, 3, 1]);
// -> Set(3) { 1, 2, 3 }

new Set([1, 2, 3, 4]);
// -> Set(4) { 1, 2, 3, 4 }

new Set([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]);
// -> Set(4) { 1, 3, 4, 2 }


In that case, the difference between the size of the set and the length of the original array will tell us whether it contains duplicates or not. If they are not equal to each other, that means the array has duplicates.

function containsDuplicate(nums: number[]): boolean {
return !(new Set(nums).size === nums.length);
};


It's obvious from the size and length comparison that this solution works, and indeed, it passes the tests.

#### Time & space complexity

My guess for the time complexity is that it's $O(n)$ , because the Set constructor iterates over each element in the array it is given as the argument.
I think that the space complexity is also $O(n)$ , because in the worst case where each element is unique, Set needs to allocate memory for each of them.

##### Using Python

We can translate this solution into Python like this as well:

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


It's now time to take a breath.

Let's look at NeetCode's solution:

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

for n in nums:
if n in hashset:
return True

The worst case is still $O(n)$ , and space complexity is $O(n)$ as well in the case of each element being unique.