How to find duplicates in an array

An array in C++ stores multiple values of the same data type in a single variable. We can also say that it's a collection of similar items. These items of the same data types in an array are its elements. We can access these elements using the index of the array.

A pictorial representation of arrays is shown below:

The length of this array is 5.
The data type of values stored in this array is an integer.

Find duplicates in an array

We are given an array of $n$ integers, and we need to print the duplicate elements from the array. A number is duplicated if it occurs more than once in the array. There are many methods to solve this problem, but we need to opt for the efficient one.

Method 1: Use a nested loop for every element. If the element occurs more than once, store it in the hash map. Otherwise, check for the next element. Its time complexity would be $O(n^2)$ .

Method 2: Count the frequency of every element, and print the element with frequency 1+. We'll require to use an unordered set and unordered map for this method since the range of integers is unknown. Its time complexity is $O(n)$ .

Method 3: Use a simple hash map. If the elements in the array are from $0$ to $n -1$ where the size of the array is of size $n$ , the array can be used as a hash map. During traversing, if an element $a$ is encountered increase the value of $a$ % $nth$ by $n$ . We can use it to find the frequency of the element by dividing $a$ % $nth$ element by size $n$ again. It's time complexity $O(n)$ .

Note: This will only work when all elements are in the range from 0 to $n-1$ where $n$ is the size of the array.

Proposed solution

Our second method is the most efficient one since it takes less time and has total correctness.

Steps

Traverse the whole array from index 0 to $n - 1$ .
Count the frequency of every element using the unordered map.
Put all the elements with a frequency of more than 1 into the set.
Return the set of elements with a frequency greater than 1.

Example

#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
unordered_set<int> findDuplicates(int arr[], int size) 
{
    int i = 0;
    unordered_map<int, int> freq;  // Creating frequency map
    while( i < size) 
    {
        freq[arr[i]]++;  //counting freq
        i++;
    }
   
    unordered_set<int> duplicates;
    for (auto const &pair: freq) 
    {
        if (pair.second > 1) //checking second parameter > 1
        {
            duplicates.insert(pair.first);
        }
    }
 
    return duplicates;
}
 
int main()
{
    int arr[] = {13, 2, 4, 2, 13, 5, 4};
    int n = sizeof(arr) / sizeof(*arr);
 
    unordered_set<int> duplicates = findDuplicates(arr, n);
    for (int i: duplicates) 
    {
        cout << i << ' ';        
    }
 
    return 0;
}

How to find duplicates in an array

Find duplicates in an array

Proposed solution

Steps

Example

Code

Explanation

Time complexity