Algorithm to find intersection of two sets without using any data structure

Question

I would like to know the algorithm to determine the intersection of two arrays of equal elements (say, integer) without using any external data structure (like hash table) efficiently (O(nlogn))?

Answer 1

sort, then iterate using an iterator to each element array:

if A[iter1] > B[iter2]: increase iter2
else if A[iter1] < B[iter2]: increase iter1
else: element is in intersection, print and increase both iters

Sorting is O(nlogn), iterating is O(n), total O(nlogn)

Answer 2

• Sort the arrays
• Loop through them and store matches

Something like...

var A = [0...N];
var B = [0...N];
var result = [];
Array.sort(A);
Array.Sort(B);
for(var x=0, y=0; x < N && y < N; x++) {
    while(A[x] < B[y] && y < N) {
        y++;
    }
    if(A[x] == B[y]) {
        result.push( B[y++] );
    }
}