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

Question

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

Answer 1

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).

Answer 2

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.