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