How to find duplicates in an array

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

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

How to find duplicates in an array

Find duplicates in an array

Proposed solution

Steps

Example

Code

Explanation

Time complexity