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.

Table Of Contents

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);

    // applying adjacent_find() function and
    // 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.