Home » Data Structure » Array Data Structure

Union and Intersection of Two Unsorted Arrays

C++ implementation to find the union and intersection of two unsorted arrays.
Submitted by Vikneshwar GK, on February 05, 2022

Consider 2 arrays that are unsorted and distinct. The task at hand is to find the union and intersection of these two arrays.

Example:

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

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

Input:
test1[] = {2, 7, 4, 8, 5}
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 using Set

Set is a data structure that stores only distinct elements. Taking this to our advantage, we can find the union of two unsorted arrays by simply inserting them into a set data structure.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to find and print Union
void findUnion(int array1[], int array2[], int length1, int length2)
{
    // Declare set
    set<int> s;

    // Inserting array elements in s
    for (int i = 0; i < length1; i++)
        s.insert(array1[i]);

    for (int i = 0; i < length2; i++)
        s.insert(array2[i]);

    cout << "Union : ";
    for (auto itr = s.begin(); itr != s.end(); itr++)
        cout << *itr << " ";
}

// 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];
    }

    findUnion(array1, array2, length1, length2);
    
    return 0;
}

Output:

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

Time Complexity: O(m*log(m)+n*log(n))

Solution 2: Finding Union using Map

Like the previous solution, where we used set data structure to our advantage, here we will use map data structure. Map stores the elements in a key-value format where the key will always be unique. Using this concept, we can find the union of two unsorted arrays. It involves inserting both the array elements into the map where the element will be the map key. Then print the keys.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to find and print Union
void findUnion(int* array1, int* array2, int length1, int length2)
{
    // Declare map
    map<int, int> m;

    // Inserting array elements in mp
    for (int i = 0; i < length1; i++)
        m.insert({ array1[i], i });

    for (int i = 0; i < length2; i++)
        m.insert({ array2[i], i });

    cout << "Union : ";
    for (auto itr = m.begin(); itr != m.end(); itr++)
        cout << itr->first << " ";
}

// 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];
    }

    findUnion(array1, array2, length1, length2);

    return 0;
}

Output:

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

Time Complexity: O(m+n)

Solution 3: Find Union and Intersection using Sorting and Searching

This is a simple approach to finding the union and intersection of two unsorted arrays. It involves the following step.

1. Union:
   1. Compare both the arrays and find the smallest one in terms of length
   2. Sort the smaller array and print them
   3. Iterate the larger array and check if its elements are present in the smaller array using binary search since the smaller array is sorted
   4. If the element is not present, then print that element
2. Intersection:
   1. Compare both the arrays and find the smallest one in terms of length
   2. Sort the smaller array
   3. Iterate the larger array and check if its elements are present in the smaller array using binary search since the smaller array is sorted
   4. If the element is present, then print that element

C++ Implementation:

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
using namespace std;

int binarySearch(int arr[], int l, int r, int x);

// Prints union of arr1[0..m-1] and arr2[0..n-1]
// Function to find and print union of two arrays
void findUnion(int array1[], int array2[], int length1, int length2)
{
    // find the smaller array and put it in array1
    if (length1 > length2) {
        int* tempp = array1;
        array1 = array2;
        array2 = tempp;

        int temp = length1;
        length1 = length2;
        length2 = temp;
    }

    // sort the smaller array
    sort(array1, array1 + length1);
    cout << "Union : ";

    // print the smaller array
    for (int i = 0; i < length1; i++)
        cout << array1[i] << " ";

    // interate through the larger array
    for (int i = 0; i < length2; i++)

        // check whether larger array elements are present in smaller array
        // print if not found
        if (binarySearch(array1, 0, length1 - 1, array2[i]) == -1)
            cout << array2[i] << " ";

    cout << endl;
}

// Function to print the intersection
void findIntersection(int array1[], int array2[], int length1, int length2)
{
    // find the smaller array and put it in array1
    if (length1 > length2) {
        int* tempp = array1;
        array1 = array2;
        array2 = tempp;

        int temp = length1;
        length1 = length2;
        length2 = temp;
    }

    // Sort the smaller array
    sort(array1, array1 + length1);

    cout << "Intersection : ";

    // interate through the larger array
    for (int i = 0; i < length2; i++)
        // check whether larger array elements are present in smaller array
        // print if found
        if (binarySearch(array1, 0, length1 - 1, array2[i]) != -1)
            cout << array2[i] << " ";

    cout << endl;
}

// Binary Search
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;

        if (arr[mid] == x)
            return mid;

        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

// 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];
    }

    findUnion(array1, array2, length1, length2);
    findIntersection(array1, array2, length1, length2);
    
    return 0;
}

Output:

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

Time Complexity: O((m+n)log(m), (m+n)log(n))