CODEWITHSUNDEEP
algorithm
Learner
Learner

Reputation: 544

Removing elements from one array from which are in another array

I have a question being asked in interview.

There are 2 arrays.

arr1 = {3,5,6,8,1,6,7};
arr2 = {5,6,8};

so the final output is 

arr1 = {3,8,1,7};

I could answer it with O(n^2) time.

Is there a better way of doing it.

Regards,

Rajesh

Upvotes: 0

Views: 32

Answers (2)

AdityaReddy
AdityaReddy

Reputation: 3645

You can do it in O(n) by using a HashSet. Add second array elements in a HashSet and iterate first array in one pass -

This will give you O(n)

Implementation in Java below. Please ignore any typos

int[] arr2 = {5,6,8};
Set toBeRemoved = new HashSet<Integer>();
for(int i:arr2){
toBeRemoved.add(i);
}
for(int i:arr1){
if(toBeRemoved.contains(i)){
//Logic to remove from array
//Or else if you dont have space contraint just add elements to a new array
}
}

Upvotes: 0

fafl
fafl

Reputation: 7385

You can do it in O(n+m) time by constructing a HashSet from the second array to use as a lookup. These lookups run in O(1) and it takes O(m) to build the set.

Then you just iterate over your first array in O(n) and keep only the desired elements.

Upvotes: 1

Related Questions