• Computer Science
• Python
• TypeScript

LeetCode Meditations: Contains Duplicate

For this problem, let's start with the description:

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

[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 }

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.

Using TypeScript, my solution was this:

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

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)

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
            hashset.add(n)

        return False

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

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

        return False

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

However, I think it's an improvement as compared to my initial solution, because instead of creating the set in one go, we can return immediately if the element is in the set as we go through adding each one.

As we have reached the end of this meditation, we can take one more deep breath. Next up is the Valid Anagram problem. Until then, happy coding.