top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+4 votes
72 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 by Mona Sharma

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

2 Answers

+2 votes

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 Nov 8, 2013 by Vikas Upadhyay
+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.
answer Nov 6, 2013 by Pankaj Agarwal
Similar Questions
+2 votes

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

+4 votes

Write a program to make AVL tree buy arranging element in array ?

+4 votes

If we delete the mth number from a circle which is composed of numbers 0, 1, …, n-1 counting from 0 at every time, what is the last number?

For example, a circle is composed of five numbers 0, 1, 2, 3, 4. If we delete the 3rd number at every time, the deleted numbers are in order of 2, 0, 4, 1, so the last remaining number is 3.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...