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;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]