Contains Duplicate - Leetcode Solution

Problem:

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

Input: nums = [1,2,3,4] Output: false

Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true

Solution:

The problem is straight forward. We need to check if there exists any duplicate element in the array. The brute force approach to solve this problem is to use two nested loops and check for the duplicate elements. But this approach will have a time complexity of O(n^2).

A more optimal approach is to use a set data structure. Set stores unique elements and thus, we can easily check if an element is already in the set. If an element is already in the set, it means that it is a duplicate. We can then return true. If we reach the end of the loop and still haven't found any duplicate, we return false.

Code:

Here is the Python code to solve the problem using the set data structure:

def containsDuplicate(nums: List[int]) -> bool:

# initialize an empty set to store unique elements
unique_set = set()

# loop through each element in the array
for num in nums:
    
    # if the element is already in the set, it's a duplicate
    if num in unique_set:
        return True
    
    # add the element to the set
    unique_set.add(num)

# if we reach here, it means that there is no duplicate
return False

Complexity Analysis:

Time complexity: O(n), where n is the length of the input array. We loop through all the elements in the array just once.

Space complexity: O(n), where n is the length of the input array. We use a set data structure to store unique elements in the array. The worst case scenario is when all elements in the array are unique and the size of the set would be equal to the size of the input array.

1