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)² 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).

Happy learning !!!