## DEV Community 👩‍💻👨‍💻 is a community of 918,681 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Bernice Waweru

Posted on • Updated on

# Contains Duplicate

## 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:
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).