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))?
-
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– Neel2012-10-12 17:14:39 +00:00Commented Oct 12, 2012 at 17:14
Add a comment
|
3 Answers
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)
Comments
- 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++] );
}
}
1 Comment
Prasanna
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).
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.
- Sort all the sets.
- Take the smallest set, and insert all the elements, and their frequencies into a map.
- 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.
