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 HashSetset = 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 HashSetset = 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; } }