Two sorted arrays A and B are given, the task is to print A Intersection B.
Intersection of the two arrays can be defined as the set containing common elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in the Intersection.
Example 1: Print Intersection of: {1, 3, 4, 6} and {1, 2, 3, 5}
Input: {1, 3, 4, 6}, {1, 2, 3, 5}
Output: 1 3
Example 2: Print Intersection of: {11, 33, 62, 105} and {1, 11, 105, 620}
Input: {11, 33, 62, 105}, {1, 11, 105, 620}
Output: 11 105
Solutions
Method 1: Modified Merge
We can solve this problem in O(n) time and O(1) space, with the help of a modified version of Merge() function from MergeSort() algorithm.
The modification in Merge() is needed because we have to consider only common elements in both the arrays; i.e. an element should be printed only if it is present in both a[] and b[].
Both arrays are also passed to removeDuplicate(), this is done to ensure that none of two have any repeated element within array. The removeDuplicate() method arranges unique element in the beginning of the array and returns new size of unique elements in the array.
Complexity
Here both arrays are traversed twice, once to remove duplicates and other to apply merge fn for printing, so time complexity is (2m+2n) or O(m+n). No auxiliary space is used in this algorithm so space complexity is O(1).