Program to print Intersection of two sorted arrays

Posted by N.K. Chauhan on Mar 31, 2024

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

Related


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

Minimize the difference between the heights of smallest and highest tower

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

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

Program to right rotate an array by 'k' elements

Move all negative numbers to beginning of the array

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

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

Find maximum and minimum element of an array

Maximum Product Subarray (Modified Kadane's Algorithm)

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