# 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);
int n = sizeof(arr2) / sizeof(arr2);
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);

// Incrementing the First element's count in it's
// corresponding index in newtable
++newtable[arr1];
// 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);
int m = sizeof(arr2) / sizeof(arr2);
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);
int n = sizeof(arr2) / sizeof(arr2);
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);
int n = sizeof(arr2) / sizeof(arr2);
// Function calling
print_intersection(arr1, arr2, m, n);
return 0;
}``````

Output:

`2 4`