Home » Data Structure » Array Data Structure

Union and Intersection of Two Sorted Arrays

C++ implementation to union and intersection of two sorted arrays.
Submitted by Vikneshwar GK, on January 27, 2022

Consider 2 arrays that are sorted in ascending order. The task at hand is to find the union and intersection of these two arrays.

Example:

Input:
test1[] = {1, 2, 4, 5, 6}
test2[] = {2, 3, 5, 7} 

Output for Union: 1 2 3 4 5 6 7
Output for Intersection: 2 5

Input:
test1[] = {2, 4, 5, 7, 8}
test2[] = {1, 2, 4, 5, 8}

Output for Union: 1 2 4 5 7 8
Output for Intersection: 2 4 5 8

Solution 1: Finding Union

Follow the given procedure to find the union of two sorted arrays:

• Use two pointers i and j pointing starting element of array1 and array2
• Compare array1[i] and array2[j]
• If array1[i]<array2[j], print array1[i] and increment i
• If array1[i]>array2[j], print array2[j] and increment j
• If array1[i]=array2[j], print any of them and increment both i and j
• Print the remaining elements of the larger array

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

void UnionArray(int array1[], int array2[], int length1, int length2)
{
    // store max value
    int max1 = array1[length1 - 1];
    int max2 = array2[length2 - 1];

    int ans = 0;

    if (max1 > max2) {
        ans = max1;
    }
    else
        ans = max2;

    int newtable[ans + 1];
    memset(newtable, 0, sizeof(newtable));

    // printing first element
    cout << array1[0] << " ";

    // Incrementing the First element's count
    // in it's corresponding index in newtable
    ++newtable[array1[0]];

    // Starting traversing the first
    // array from 1st index till last
    for (int i = 1; i < length1; i++) {
        // Checking whether current element
        // is not equal to it's previous element
        if (array1[i] != array1[i - 1]) {
            cout << array1[i] << " ";
            ++newtable[array1[i]];
        }
    }

    // Finding only non common
    // elements from 2nd array
    for (int j = 0; j < length2; j++) {
        // By checking whether it's already
        // present in newtable or not
        if (newtable[array2[j]] == 0) {
            cout << array2[j] << " ";
            ++newtable[array2[j]];
        }
    }
}

// Main function
int main()
{
    int array1[100], array2[100], length1, length2;
    
    cout << "Enter Number of elements for array 1: ";
    cin >> length1;

    for (int i = 0; i < length1; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array1[i];
    }

    cout << "Enter Number of elements for array 2: ";
    cin >> length2;

    for (int j = 0; j < length2; j++) {
        cout << "Enter element " << j + 1 << ":";
        cin >> array2[j];
    }

    UnionArray(array1, array2, length1, length2);

    return 0;
}

Output:

Enter Number of elements for array 1: 5
Enter element 1:1
Enter element 2:2
Enter element 3:4
Enter element 4:5
Enter element 5:6
Enter Number of elements for array 2: 4
Enter element 1:2
Enter element 2:3
Enter element 3:5
Enter element 4:7
1 2 4 5 6 3 7 

Time Complexity: O(m+n)

Solution 2: Finding Intersection

Follow the given procedure to find the intersection of two sorted arrays:

• Use two pointers i and j pointing starting element of array1 and array2
• Compare array1[i] and array2[j]
• If array1[i]<array2[j], increment i
• If array1[i]>array2[j], increment j
• If array1[i]=array2[j], print any of them and increment both i and j

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

void arrayIntersection(int array1[], int array2[], int length1, int length2)
{
    int i = 0, j = 0;
    while (i < length1 && j < length2) {
        if (array1[i] < array2[j])
            i++;
        else if (array2[j] < array1[i])
            j++;
        else /* if arr1[i] == arr2[j] */
        {
            cout << array2[j] << " ";
            i++;
            j++;
        }
    }
}

// main function
int main()
{
    int array1[100], array2[100], length1, length2;
    
    cout << "Enter Number of elements for array 1: ";
    cin >> length1;

    for (int i = 0; i < length1; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array1[i];
    }

    cout << "Enter Number of elements for array 2: ";
    cin >> length2;

    for (int j = 0; j < length2; j++) {
        cout << "Enter element " << j + 1 << ":";
        cin >> array2[j];
    }

    arrayIntersection(array1, array2, length1, length2);

    return 0;
}

Output:

Enter Number of elements for array 1: 5
Enter element 1:2
Enter element 2:4
Enter element 3:5
Enter element 4:7
Enter element 5:8
Enter Number of elements for array 2: 5
Enter element 1:1
Enter element 2:2
Enter element 3:4
Enter element 4:5
Enter element 5:8
2 4 5 8

Time Complexity: O(m+n)