Find duplicates in a given array when elements are not limited to a range

Difficulty Level Easy
Frequently asked in Adobe Amazon Factset MAQ UHG Optum
Array HashingViews 3632

The problem “Find duplicates in a given array when elements are not limited to a range” states that you have an array consisting of n integers. The problem statement it to find out the duplicate elements if present in the array. If no such element exists return -1.

Example

Find duplicates in a given array when elements are not limited to a range

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

Explanation

In this array 2 and 7 are the only duplicate elements.

[134, 567, 134, 456, 1000, 567, 7]
134, 567

Explanation

In this array 134 and 567 are the only duplicate elements.

Algorithm to find duplicate elements in an array

  1. Declare map.
  2. Store the array’s element and its frequency in a map.
  3. Declare the Boolean variable duplicate to check if a duplicate element exists or not.
  4. Iterate over the map and check for which element has a frequency greater than 1.
  5. If the frequency is greater than 1, print the element and initialize duplicate to true.
  6. Check if the duplicate is false if the condition satisfies then print -1.

Explanation

We have given a problem in which we have to determine the duplicate elements in an array and print those elements. For this, we are going to use a HashMap for storing the frequencies of each array element. Frequencies, which are greater than 1, means the number repeats itself in the array. That means the duplicacy of that number.

We have passed two arguments as an array and its length. Now declare one more variable that will be Boolean variable initialized as false. Then later check it, if we will not find any duplicate element then duplicate remains false else it will be true. Then using this map, find out the element which has a frequency is greater than 1, we will be printing those elements. And that’s how we find the duplicate elements in an array.

Let us consider an example:

arr [ ] = {2,4,6,3,1,2,4,7};

i=0, arr[i]=2; freq={2:1}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

i=5, arr[i]=2; freq={2:2,4:1,6:1,3:1,1:1}// increasing the frequency of ‘2’ from 1 to 2,

i=6, arr[i]=4; freq={2:2,4:2,6:1,3:1,1:1}// increasing the frequency of ‘4’ from 1 to 2,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

we have freq in map: {2:2,4:2,6:1,3:1,1:1,7:1}

Now iterate over the map, and find out which value have frequency is greater than 1. We already here initialized a Boolean variable duplicate as false, so when we check of which frequency is greater than 1 we are going to update duplicate as true. And if we come out of the loop having duplicate as false, it means duplicate element doesn’t exist in an array.

Clearly, 2 and 4 have a frequency greater than means they are duplicate elements.

And our output becomes [2 4 ]. So this was an example of how we find duplicate elements in an array.

Code

C++ code to find duplicate elements in an array

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}

4 2

Java code to find duplicate elements in an array

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}

2 4

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Thus the “Find duplicates in a given array when elements are not limited to a range” problem has linear time complexity.

Space Complexity

O(n) where “n” is the number of elements in the array. The space complexity is also linear because in the worst-case we may have all distinct elements.

Translate »