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.
| package com.cb.arrays; | |
| import java.util.Arrays; | |
| import java.util.stream.Collectors; | |
| /* | |
| * Time: O(n+m) | |
| * Space: O(1) | |
| * */ | |
| public class A7_IntersectionOfTwoSortedArrays { | |
| private static void printIntersection(int[] a, int[] b, int n1, int n2) { | |
| int i = 0, j = 0; | |
| n1 = removeDuplicate(a, n1); | |
| n2 = removeDuplicate(b, n2); | |
| // while both arrays have elements to traverse | |
| while (i < n1 && j < n2) { | |
| // Print only if both arrays have common element | |
| if (a[i] == b[j]) { | |
| System.out.print(a[i] + " "); | |
| i++; | |
| j++; | |
| } else if (a[i] <= b[j]) | |
| i++; | |
| else | |
| j++; | |
| } | |
| } | |
| // Just to print output array | |
| private static void printArray(int[] arr) { | |
| System.out.println(Arrays.stream(arr).mapToObj(Integer::toString). | |
| collect(Collectors.joining(","))); | |
| } | |
| // works for sorted arrays only | |
| private static int removeDuplicate(int[] a, int n) { | |
| if (n < 2) | |
| return n; | |
| int uniqueIndex = 0; | |
| int lastUniqueElement = a[0]; | |
| for (int i = 1; i < n; i++) { | |
| if (a[i] != lastUniqueElement) { | |
| uniqueIndex++; | |
| a[uniqueIndex] = a[i]; | |
| lastUniqueElement = a[i]; | |
| } | |
| } | |
| return uniqueIndex + 1; | |
| } | |
| // Test | |
| public static void main(String[] args) { | |
| int[] a = {1, 3, 4, 6}; | |
| int[] b = {1, 2, 3, 5}; | |
| printIntersection(a, b, a.length, b.length); // 1 3 | |
| System.out.println(); | |
| int[] a1 = {11, 33, 62, 105}; | |
| int[] b1 = {1, 11, 105, 620}; | |
| printIntersection(a1, b1, a1.length, b1.length); // 11 105 | |
| } | |
| } |
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).