Two sorted arrays A and B are given, the task is to print A U B.
Union of the two arrays can be defined as the set containing all the unique elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in the union.
Example 1: Print Union of: {1, 3, 4, 6} and {1, 2, 3, 5}
Input: {1, 3, 4, 6}, {1, 2, 3, 5}
Output: 1 2 3 4 5 6
Example 2: Print Union of: {11, 33, 62, 105} and {1, 11, 105, 620}
Input: {11, 33, 62, 105}, {1, 11, 105, 620}
Output: 1 11 33 62 105 620
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 is needed to handle situations, when one or more element(s) are common in both the arrays; i.e. if any element is present in both a[] and b[] it should be printed only once.
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).