Intersection of two arrays
Today’s problem involves two arrays, which are not sorted. All we need to find is intersection of two arrays. By finding intersection, we mean find common elements in given two arrays. For example,
Array1 => 1,4,3,2,5,6 Array2 => 3,2,1,5,6,7,8,10 Intersection of array1 and array2 => 1,3,2,5,6
Ways to find intersection of two arrays
Method 1 : Sort array and then use binary search
As arrays given are unsorted, sort one of the array, preferably the larger one. Then search each element of other array in first sorted array using binary search. If element is present, it goes into intersection array else not.
Complexity of this method to find intersection is O(N log N) for sorting and then M log N for searching. Effective time complexity becomes O((N+M) log N) which is not optimal.
Method 2 : Sort and use merge to find common elements
Again this method, sort two arrays first. Then use two pointers to scan both arrays simultaneously. (Please refer to merge part of merge sort). Difference is we have to put in result only those elements which are common, instead of all.
Complexity of this method is O(N log N) + O ( M log M ) for sorting and then O(M+N) for scanning both arrays which is worst then the first method.
Method 3: Use hash
Create a hash with key as elements from smaller array (saves space). Then scan through other other and see if the element is present in hash. If yes, put into intersection array else not.
This method has complexity of O(N) where N is number of elements in bigger elements and extra space complexity of O(M) where M is number of elements in smaller array.
These method to find intersection of two arrays do not work when there are duplicate elements in any of the array as they will be part of intersection array only once. While in other methods, duplicate elements will be present more number of times then they should be.
Please share if there is something wrong or missing. we would love to hear from you. If you want to contribute to website, please refer to publishing at algorithm and me