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?