Problem
Find Union and Intersection of two sorted arrays
Example
For example, if the input arrays are:
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}.
Solution
Algorithm Union(arr1[], arr2[]):
For union of two arrays, follow the following merge procedure.
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
- If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
- If both are same then print any of them and increment both i and j.
- Print remaining elements of the larger array.
#include<stdio.h>
#include<stdio.h>
int printUnion(int arr1\[\], int arr2\[\], int m, int n)
{
int i = 0, j = 0;
while(i < m && j < n)
{
if(arr1\[i\] < arr2\[j\])
printf(" %d ", arr1\[i++\]);
else if(arr2\[j\] < arr1\[i\])
printf(" %d ", arr2\[j++\]);
else
{
printf(" %d ", arr2\[j++\]);
i++;
}
}
// Print remaining elements of the larger array
while(i < m)
printf(" %d ", arr1\[i++\]);
while(j < n)
printf(" %d ", arr2\[j++\]);
}
Time Complexity: O(m+n)
Algorithm Intersection(arr1[], arr2[]):
For Intersection of two arrays, print the element only if the element is present in both arrays.
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then increment i.
- If arr1[i] is greater than arr2[j] then increment j.
- If both are same then print any of them and increment both i and j.
#include<stdio.h>
int printIntersection(int arr1\[\], int arr2\[\], int m, int n)
{
int i = 0, j = 0;
while(i < m && j < n)
{
if(arr1\[i\] < arr2\[j\])
i++;
else if(arr2\[j\] < arr1\[i\])
j++;
else // if arr1\[i\] == arr2\[j\]
{
printf(" %d ", arr2\[j++\]);
i++;
}
}
}
Time Complexity: O(m+n)
References