How To Remove Duplicate From Array Without Using Any Collection Or Function

Admin | Wed, 03 Jun, 2020 | 566

How to remove duplicates from an array

In many interview questions it is asked to remove duplicates, but they will keep one condition that we can not use any collections or functions to do so, we have to do only and only in array.

So how can we do it ?

Actually this question was recently asked to one of my friend in interview

Question was to remove duplicates from an integer array without using any collection API classes like Set or LinkedHashSet, which can make this task trivial. In general, if you need to do this for any project work, I suggest better using Set interface, particularly linkedHashSet, because that also keep the order on which elements are inserted into Set. Only for technical interview perspective, you need to do this using either loops or recursion,  depending upon what is your strongest area.
The main problem, while dealing with an array is not finding duplicates, it's about removing them. Since an array is a static, fixed length data structure, you can not change its length. This means, deleting an element from an array requires creating a new array and copying content into that array.
 

If your input array contains lots of duplicates then this may result in lots of temporary arrays. It also increases cost of copying contents, which can be very bad. Given this restriction, you need to come out with a strategy to minimize both memory and CPU requirements.

So how to do it ?

We can do it by checking and changing value of repeated value.

For and example if we have an array like :- {1,2,1,3,1,5} -> {1,2,-1,3,-1,5}.

To do this we need to know little of hasing, if you don't know about hashing try searching it in search bar and give a look at it.

#include <bits/stdc++.h>
 
using namespace std;
int main(int argc, char** argv)
{
    int size=6;
    int arr[6]={1,2,1,3,1,4};
    for(int i=0;i<size;i++){
        for(int j=i+1;j<size;j++){
            if(arr[i]==arr[j])
            arr[j]=-1;
        }
    }
    
    for(int i=0;i<size;i++){
        cout<<arr[i]<<" ";
    }
}

This solution is not perfect and has some serious limitations but you can use it to get your answer.

0 comments
Leave a comment