Program to print Union of two sorted arrays

Posted by on Mar 31, 2024

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).

Related


Maximum Product Subarray (Modified Kadane's Algorithm)

Find maximum and minimum element of an array

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Find duplicates in O(n) time and O(1) extra space

Program to right rotate an array by 'k' elements

Find largest sum contiguous sub-array (Kadane's Algorithm)

Move all negative numbers to beginning of the array

Alternating +ve & -ve in array in O(1) time (maintaining order)

Minimize the difference between the heights of smallest and highest tower

Find duplicates in O(n) time and O(n) extra space.