How do i solve this question Let A and B be two nonsorted ar

How do i solve this question?

Let A and B be two non-sorted arrays. Assume that all the numbers in A are pairwise disjoint and the same is true for B. Write an efficient as you can algorithm that lists all the elements (values) of B that that do not appear in A. Example: A = [4, 2, 5, 3, 7, 1], B = [13, 7, 4, 21, 5, 3]. The values of B that do not appear in A are 13, 21.

Solution

Step 1:

Initially sort the arrays using one of those O(n log n) techniques. At present you have two arrays which are sorted.

Step 2:

Start 2 indexes, a_index, b_index. Initially both are 0,

Read B[b_index], scan the elements in array A and keep comparing them to B[b_index] value. You just have to scan until you reach a value in A which is more than or equal to B[b_index] value. If its equal to, ignore it. If not add print it out.

Step 3:

Increment b_index, but your a_index will remain from where you stopped last time.

Repeat step 2.

Continue to doing step 2 and 3 for all elements in B.

Like this, you are now traversing elements in A and B once. So if A has n elements and B has n elements. You are just traversing 2n elements.

The complexity will be O(n log n + 2n) and for large n O(nlogn)