Algorithms | Made Easy Full Syllabus Test

Question

Consider two arrays A and B which are integer types. Array A has n distinct values in it and array B also has n distinct values in it, but A and B can share some values. What is the worst-case running time to compute A – B?

 

Approach:

Create array H_A.
Scan A and set H_A[A[i]] = 1

Scan B and set H_A[B[i]] = 0, if H_A[B[i]] is 1.
Scan H_A and get A-B.

Time complexity O(n).

However, the given solution is :

Is it always assumed that the algorithm should work without any auxiliary space?

Answer 1

Actually it should be given that we are allowed to use some extra space or in solving the problem.

In this question your approach is correct as we can find the intersection in O(n+n)=O(2n)=O(n) time .

and then remove them using hash function ,

And in fact in cpp there is an inbuild set difference operation we have works in linear time depending on range of number.

http://www.cplusplus.com/reference/algorithm/set_difference/

So given space we can do it less time and it is always a trade off between time and space.