2

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

Charles
  • 50,943
  • 13
  • 104
  • 142
Neel
  • 9,913
  • 16
  • 52
  • 74
  • No, it was an interview question. The interviewer asked me to solve it without using any data structure. If I sort the two arrays, scan the first one and do the binary search of the second one, we get it in O(nlogn) time. Can we do it without using binary search? – Neel Oct 12 '12 at 17:14

3 Answers3

14

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)

amit
  • 175,853
  • 27
  • 231
  • 333
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++] );
    }
}
Louis Ricci
  • 20,804
  • 5
  • 48
  • 62
  • In this case, time complexity would be O(n^2). The question is how to achieve matching elements in linearithmic time complexity which is (nlogn). – Prasanna May 11 '20 at 04:10
0

Intersection of n sets

Given n sets of integers of different sizes. Each set may contain duplicates also. How to find the intersection of all the sets. If an element is present multiple times in all the sets, it should be added that many times in the result.

For example, consider there are three sets {1,2,2,3,4} {2,2,3,5,6} {1,3,2,2,6}. The intersection of the given sets should be {2,2,3}

The following is an efficient approach to solve this problem.

  1. Sort all the sets.
  2. Take the smallest set, and insert all the elements, and their frequencies into a map.
  3. For each element in the map do the following …..a. If the element is not present in any set, ignore it …..b. Find the frequency of the element in each set (using binary search). If it less than the frequency in the map, update the frequency …..c. If the element is found in all the sets, add it to the result.

Time Complexity: Let there be ‘n’ lists, and average size of lists be ‘m’. Sorting phase takes O( n* m *log m) time (Sorting n lists with average length m). Searching phase takes O( m * n * log m) time . ( for each element in a list, we are searching n lists with log m time). So the overall time complexity is O( nmlog m ).

Auxiliary Space: O(m) space for storing the map.

Mohammed Raish Sayyed
  • 1
  • 2