Solution For Contains Duplicate

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.

Step by Step Implementation For Contains Duplicate

import java.util.HashSet;

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        // create a set to store unique elements
        HashSet set = new HashSet<>();
        
        // iterate through array and add elements to set
        // if an element is already in the set, return true
        for (int i : nums) {
            if (!set.add(i)) {
                return true;
            }
        }
        
        // if we get through the whole array and don't find a duplicate, return false
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # create a set to store unique values 
        unique_values = set() 
        
        # loop through each value in the list 
        for value in nums: 
            
            # if the value is not in the set, add it 
            if value not in unique_values: 
                unique_values.add(value) 
                
            # if the value is in the set, return True 
            else: 
                return True 
                
        # if the loop finishes without returning True, return False 
        return False

var containsDuplicate = function(nums) {
    // create a map to store values
    const map = {};
    
    // iterate over nums
    for (const num of nums) {
        // check if map already contains num
        if (map[num]) {
            // if so, return true
            return true;
        } else {
            // if not, add num to map
            map[num] = true;
        }
    }
    
    // if we get through the whole array and don't find a duplicate, return false
    return false;
};

bool containsDuplicate(vector& nums) {
    // create a set to store unique elements 
    unordered_set set; 
      
    // traverse the input array 
    for (int i = 0; i < nums.size(); i++) { 
          
        // if element is already present in the set 
        // then return true 
        if (set.find(nums[i]) != set.end()) 
            return true; 
              
        // insert the element in the set 
        set.insert(nums[i]); 
    } 
      
    // no duplicate element found 
    return false; 
}

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        
        //check for empty or null array
        if(nums == null || nums.Length == 0){
            return false;
        }
        
        //create a HashSet to store unique elements
        HashSet set = new HashSet();
        
        //loop through array and add elements to HashSet
        //if element is already present in HashSet, return true
        //else add element to HashSet
        foreach(int num in nums){
            if(set.Contains(num)){
                return true;
            }
            else{
                set.Add(num);
            }
        }
        
        //if no duplicates found, return false
        return false;
    }
}