## Instructions

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

Input: nums = [1,2,3,1]

Output: true

## Approach

We can solve this problem using several approaches.

A brute force approach would be to compare each element in the array with other elements to determine if they are the same.

This approach yields a time complexity of O(n)^{2} because we have to go through each element. The space complexity is O(1) because we do not use extra memory.

```
def contains_duplicate(nums):
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
if nums[i] == nums[j]: return True
return False
```

However, we can improve this solution by making a trade-off on space complexity.

We can use a set and compare the lengths of the array to determine if there a duplicates. A set contains only unique elements, therefore, if there are duplicates the length of the new array is smaller than the original array.

```
def containsDuplicate(self, nums):
new_nums = set(nums)
if len(new_nums)<len(nums):
return True
else:
return False
```

#### One Liner

```
def containsDuplicate(self, nums):
return True if len(set(nums))<len(nums) else False
```

This solution has a time complexity of O(n) and space complexity of O(n).

## Approach 2

We can also use a hashmap or hashset and lookup if we have already encountered an element. If we have, we immediately return True because there is a duplicate.

```
def containsDuplicate(self, nums):
hashset = set()
for i in nums:
if i in hashset:
return True
else:
hashset.add(i)
return False
```

We could also use a hashmap as follows:

```
def containsDuplicate(self, nums):
hashmap = {}
for i in nums:
if i in hashmap:
hashmap[i] = hashmap.get(i)+1
else:
hashmap[i] = 1
for k,v in hashmap.items():
if v > 1: return True
return False
```

The dictionary has a key-value pair where the element is the key and the value is the number of occurrence of a given element. If an element appears more than once then there is a duplicate and we return True.

This solution also has a time complexity of O(n) and space complexity of O(n).

## Top comments (0)