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}
Alternative Solution: Merge Sort
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.
Read full article from Intersection of n sets | GeeksforGeeks
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}
Alternative Solution: Merge Sort
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.
vector <int> getIntersection(vector < vector <int> > &sets){ vector <int> result; // To store the reaultant set int smallSetInd = 0; // Initialize index of smallest set int minSize = sets[0].size(); // Initialize size of smallest set // sort all the sets, and also find the smallest set for (int i = 1 ; i < sets.size() ; i++) { // sort this set sort(sets[i].begin(), sets[i].end()); // update minSize, if needed if (minSize > sets[i].size()) { minSize = sets[i].size(); smallSetInd = i; } } map<int,int> elementsMap; // Add all the elements of smallest set to a map, if already present, // update the frequency for (int i = 0; i < sets[smallSetInd].size(); i++) { if (elementsMap.find( sets[smallSetInd][i] ) == elementsMap.end()) elementsMap[ sets[smallSetInd][i] ] = 1; else elementsMap[ sets[smallSetInd][i] ]++; } // iterate through the map elements to see if they are present in // remaining sets map<int,int>::iterator it; for (it = elementsMap.begin(); it != elementsMap.end(); ++it) { int elem = it->first; int freq = it->second; bool bFound = true; // Iterate through all sets for (int j = 0 ; j < sets.size() ; j++) { // If this set is not the smallest set, then do binary search in it if (j != smallSetInd) { // If the element is found in this set, then find its frequency if (binary_search( sets[j].begin(), sets[j].end(), elem )) { int lInd = lower_bound(sets[j].begin(), sets[j].end(), elem) - sets[j].begin(); int rInd = upper_bound(sets[j].begin(), sets[j].end(), elem) - sets[j].begin(); // Update the minimum frequency, if needed if ((rInd - lInd) < freq) freq = rInd - lInd; } // If the element is not present in any set, then no need // to proceed for this element. else { bFound = false; break; } } } // If element was found in all sets, then add it to result 'freq' times if (bFound) { for (int k = 0; k < freq; k++) result.push_back(elem); } } return result;}