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 !!!