DEV Community 👩‍💻👨‍💻

Bernice Waweru
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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

One Liner

def containsDuplicate(self, nums):
    return True if len(set(nums))<len(nums) else False
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)

🌚 Life is too short to browse without dark mode