# Check If Array Contains Duplicates in C++

In this article, we will discuss different ways to check if a C++ array contains duplicates or not.

## Problem Description

We have given an array that contains n numbers of an element. Now, we have to check whether the array contains duplicates or not.

• If the given array contains duplicates, we have to print The Array contains duplicates.
• If the given array doesn’t contains duplicates, we have to print The Array doesn’t contains duplicate.

Input

`int arr[] = {34, 49, 56, 21, 19, 49, 58};`

As this array contains the duplicates (value 49). Therefore, the output should be,

```The Array contains duplicates
```

There are many ways to check if an array contains duplicate elements or not. Let’s discuss each method one by one.

## Check if array contains duplicates using Iterative approach with two loop

In this approach, the array is iterated by using two loops. The first loop is used to pick up each element in array, while the second loop is used to compare the picked element with further elements. If any element is found to exist more than once, then the flag is changed and indicates that the array contains duplicate elements.

`Time Complexity: O(n^2)`
`Space Complexity: O(1)`

```#include<iostream>
#include<algorithm>

using namespace std;

bool containsDuplicate(int arr[], int size)
{
bool flag = false;
//Iterate the loop for checking duplicates
for(int i=0;i<size;i++)
{
for(int j=i+1;j<size;j++)
{
// comparing array elements
if(arr[i]==arr[j])
{
flag = true;
}
}
}
if(flag==true)
{
return true;
}
else
{
return false;
}
}

int main()
{
//define an array
int arr[] = {34,49,56,21,19,49,58};

//calculating size of array
int size = sizeof(arr)/sizeof(arr[0]);

//if duplicates are present in array
if(containsDuplicate(arr,size))
{
cout<<"The Array contains duplicates" << endl;
}
else
{
cout<<"The Array doesn't contains duplicate" << endl;
}

return 0;
}```

Output

```The Array contains duplicates.
```

In the above example, we confirmed if the array contains duplicates or not.

## Check if array contains duplicates using sort() function

In this approach, first we sort the array with sort() function. As a result all the duplicates will be placed adjacent to each other. Now with a for loop we check whether the adjacent elements are equal are not. If duplicate elements are found then the flag is changed. The flag is indication of presence of duplicate elements in an array.

`Time Complexity: O(n log(n))`
`Space Complexity: O(1)`

```#include<iostream>
#include<algorithm>

using namespace std;

bool containsDuplicate(int arr[], int size)
{
bool flag = false;
//sorting of array using sort() function
sort(arr, arr+size);

for(int i=0;i<size;i++)
{
// comparing adjacent elements of array
if(arr[i]==arr[i+1])
{
flag = true;
}
}
return flag;
}

int main()
{
//define an array
int arr[] = {34,49,56,21,19,49,58};

//calculating size of array
int size = sizeof(arr)/sizeof(arr[0]);

//if duplicates are present in array
if(containsDuplicate(arr,size))
{
cout<<"The Array contains duplicates" <<endl;
}
else
{
cout<<"The Array doesn't contains duplicate" <<endl;
}

return 0;
}```

Output

```The Array contains duplicates.
```

In the above example, we confirmed if the array contains duplicates or not.

## Check if array contains duplicates using map

In this approach, the unordered map is used, which contains key-value pairs. For each iteration in array the value of array element in map is incremented by 1. If the element is exist single time then the value of the element is 1. Whereas, if it exists more than one time then the value of the element is greater than 1 and then the flag is changed. This flag indicates the array contains duplicates. The time complexity is O(n) and space complexity is O(n).

`Time Complexity: O(n)`
`Space Complexity: O(n)`

```#include<iostream>
#include<unordered_map>

using namespace std;

bool containsDuplicate(int arr[], int size)
{
bool flag = false;

// initialize map
unordered_map<int,int> map;

// inserting array elements in map
for(int i=0; i<size; i++)
{
//increment the value
map[arr[i]]++;

//checking for duplicates
if(map[arr[i]]>1)
{
flag = true;
break;
}
}
return flag;
}

int main()
{
//define an array
int arr[] = {34,49,56,21,19,49,58};

//calculating size of array
int size = sizeof(arr)/sizeof(arr[0]);

//if duplicates are present in array
if(containsDuplicate(arr,size))
{
cout<<"The Array contains duplicates" << endl;
}
else
{
cout<<"The Array doesn't contains duplicate" << endl;
}

return 0;
}```

Output

```The Array contains duplicates.
```

In the above example, we confirmed if the array contains duplicates or not.

## Check if array contains duplicates using set

In this approach, a set is constructed which contains elements of array. The set have property to retain only distinct elements. Now we compare the size of set and size of array. If both are equal than array contains unique elements, otherwise the array contains duplicate elements.

`Time Complexity: O(n)`
`Space Complexity: O(n)`

```#include <iostream>
#include <unordered_set>

using namespace std;

bool containsDuplicate(int arr[], int size)
{
// initialize set with array elements as a input
std::unordered_set<int> set(arr,arr+size);

// compare the sizes of set and array
return (size != set.size());
}

int main()
{
//define an array
int arr[] = {34,49,56,21,19,49,58};
//calculating size of array
int size = sizeof(arr) / sizeof(arr[0]);

//if duplicates are present in array
if(containsDuplicate(arr,size))
{
cout<<"The Array contains duplicates" <<endl;
}
else
{
cout<<"The Array doesn't contains duplicate"<<endl;
}

return 0;
}```

Output

```The Array contains duplicates.
```

In the above example, we confirmed if the array contains duplicates or not.

## Check if array contains duplicates using adjacent_find() function

In this approach, the adjacent_find() function is used to detect any equal adjacent elements are present in an array or not. If adjacent elements are present then the function returns the iterator to the first duplicate, otherwise returns the iterator to the end of array. But for this, first we need to sort the array elements.

`Time Complexity: O(n)`
`Space Complexity: O(1)`

```#include <iostream>
#include <algorithm>

using namespace std;

bool containsDuplicate(int arr[], int size)
{
// sorting of array using sort() function
sort(arr,arr+size);

// compare it with array pointer
bool result = (adjacent_find(arr, arr + size) != arr + size);

return result;
}

int main()
{
//define an array
int arr[] = {34,49,56,21,19,49,58};

//calculating size of array
int size = sizeof(arr) / sizeof(arr[0]);

//if duplicates are present in array
if(containsDuplicate(arr,size))
{
cout<<"The Array contains duplicates" << endl;
}
else
{
cout<<"The Array doesn't contains duplicate" << endl;
}

return 0;
}
```

Output

```The Array contains duplicates.
```

In the above example, we confirmed if the array contains duplicates or not.

## Check if array contains duplicates using unique() function

In this approach, the unique() function is used to remove adjacent duplicates in a sorted array. First sort the array and then use unique() function. The unique() function return an iterator. If array doesn’t contains duplicate then the returned iterator points to the end of the array, otherwise iterator points somewhere else in array.

`Time Complexity: O(n)`
`Space Complexity: O(1)`

```#include <iostream>
#include <algorithm>

using namespace std;

bool containsDuplicate(int arr[], int size)
{
//sorting of array using sort() function
sort(arr, arr+size);

// applying unique() function and compare it
// with array pointer
bool result = (unique(arr, arr + size) != arr + size);

return result;
}

int main()
{
//define an array
int arr[] = {34,49,56,21,19,49,58};

//calculating size of array
int size = sizeof(arr) / sizeof(arr[0]);

//if duplicates are present in array
if(containsDuplicate(arr,size))
{
cout<<"The Array contains duplicates" <<endl;
}
else
{
cout<<"The Array doesn't contains duplicate" <<endl;
}
return 0;
}```

Output

```The Array contains duplicates.
```

In the above example, we confirmed if the array contains duplicates or not using unique() function.

## Summary

In this article we have seen various methods for checking duplicate elements in an array using STL functions and STL containers. Each method have its own time and space complexity. Happy Learning.

### 2 thoughts on “Check If Array Contains Duplicates in C++”

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top