# Delete all element from one array which are already in another ?

79 views

You have two arrays A1 and A2. Delete all element from A1 which are already in A2 and return new array.

posted Nov 4, 2013

Good Solutions.
A1 contains M element
A2 contains N element

Sol:1 => If arrays are already sorted than it would be easy to use merge algorithm with one modification where if elements are same do not add it.
Complexity O(N+M)

Sol:2 => if only A1 is sorted than it would be easy to binary search and delete element
Complexity O(N logM))

Sol:3 => if dataset is smaller than sorting can be done and any of above algorithm can be used
Not good idea

Sol:4 => If dataset is large and not sorted than A1's elements can be stored in a hash table and deleted and hash table can be coverted back to array.
Not good idea

For Sol:3 and Sol:4
Create binary tree of array A2.
Complexity O(N logN).

Now Search element of A1 in binary tree
Complexity O(log M).

Final complexity
O(nlogn).

+1 vote

There are few ways to handle it which depends on dataset and problem

• If arrays are already sorted than it would be easy to use merge algorithm with one modification where if elements are same do not add it
• if only A1 is sorted than it would be easy to binary search and delete element
• if dataset is smaller than sorting can be done and any of above algorithm can be used
• If dataset is large and not sorted than A1's elements can be stored in a hash table and deleted and hash table can be coverted back to array.
Similar Questions

1,1,2,2,2,6,6,6,7,7,7,7,7,7,7,8,8,9,9,9

Example:
Input = 1 Output=0 (First index of 1).
Input = 2 Output=2 (First index of 2).
Input = 6 Output= 5 (First index of 6).
Input = 7 Output= 8 (First index of 7).
Input = 8 Output=15 (First index of 8).
Input = 9 Output=17 (First index of 9).