Find Union and Intersection of Two Arrays in C
Union
You can find the union of the two sorted arrays using the join merge method on arr1[] and arr2[].
- Use two index variables i and j with initial values i = 0 and j = 0.
- If arr1[i] is less than arr2[j], output arr1[i] and increment i.
- If arr1[i] is greater than arr2[j], print arr2[j] and increment j.
- If both are equal, print one or the other and increment both i and j.
- print the rest of the elements.
For example:
#include <stdio.h>
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void 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++]); }
int main() {
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printUnion(arr1, arr2, m, n);
getchar();
return 0; }
Output:
1 2 3 4 5 6 7
Time Complexity: O(m + n)
Auxiliary Space: O(1)
Handling duplicates in one of the arrays:
The code above does not handle duplicates in any array. To deal with duplicates, check each element to see if its adjacent elements are the same.
// C program for the above approach
#include <stdio.h>
#include <string.h>
static void UnionArray(int arr1[], int arr2[], int l1, int l2) {
// Taking max element present in either array
int m = arr1[l1 - 1];
int n = arr2[l2 - 1];
int ans = 0;
if (m > n)
ans = m;
else
ans = n;
// Finding elements from 1st array (non duplicates
// only). Using another array for storing union elements
// of both arrays Assuming max element present in array
// is not more than 10^7
int newtable[ans + 1];
for (int i = 0; i < ans + 1; i++)
newtable[i] = 0;
// First element is always present in final answer
printf("%d ", arr1[0]);
// Incrementing the First element's count in it's
// corresponding index in newtable
++newtable[arr1[0]];
// Starting traversing the first array from 1st index
// till last
for (int i = 1; i < l1; i++) {
// Checking whether current element is not equal to
// it's previous element
if (arr1[i] != arr1[i - 1]) {
printf("%d ", arr1[i]);
++newtable[arr1[i]]; } }
// Finding only non common elements from 2nd array
for (int j = 0; j < l2; j++) {
// By checking whether it's already resent in
// newtable or not
if (newtable[arr2[j]] == 0) {
printf("%d ", arr2[j]);
++newtable[arr2[j]]; } } }
// Driver Code
int main() {
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 4, 5 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
UnionArray(arr1, arr2, n, m);
return 0;
}
Output:
1 2 3 4 5
Intersection
The intersection of the arr1 and arr2 arrays you can use the following method to find the intersection of two permuted arrays.
- Use two index variables i and j with initial values i = 0 and j = 0.
- If arr1[i] is less than arr2[j], increment i.
- Increase j if arr1[i] is greater than arr2[j].
- Print one of these, and if i and j are the same, increment both.
For example:
#include <stdio.h>
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void 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++;
}
}
}
/* Driver program to test above function */
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
printIntersection(arr1, arr2, m, n);
getchar();
return 0;
}
Output:
2 5
Handling duplicates with arrays:
The code above does not handle arrays with duplicate elements. Duplicate elements should not be counted at intersections. To handle the copy, check if there is a continuous component in the convergence list. An implementation of this strategy is shown below.
// C++ program to find intersection of two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void print_intersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
set<int> s; //set for handling duplicate elements in intersection list
while (i < m && j < n) {
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else /* if arr1[i] == arr2[j] */
{
s.insert(arr2[j]); //insertion in set s
i++;
j++; } }
for(auto itr: s) //printing intersection set list
{
cout<<itr<<" ";
} }
/* Driver code */
int main()
{
int arr1[] = { 1, 2, 2, 3, 4 };
int arr2[] = { 2, 2, 4, 6, 7, 8 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
// Function calling
print_intersection(arr1, arr2, m, n);
return 0;
}
Output:
2 4