CODEWITHSUNDEEP
algorithmsorting
Neel
Neel

Reputation: 10143

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

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

Upvotes: 2

Views: 5719

Answers (3)

Mohammed Raish Sayyed
Mohammed Raish Sayyed

Reputation: 1

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.

Upvotes: 0

amit
amit

Reputation: 178451

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)

Upvotes: 14

Louis Ricci
Louis Ricci

Reputation: 21086

  • 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++] );
    }
}

Upvotes: 2

Related Questions