Find the Union and Intersection of the Two Sorted Arrays

Understanding the Problem

The goal is to find the union and intersection of two sorted arrays using different methods.

Method 1: Using Two Pointers

This method uses two pointers to traverse both arrays and find union and intersection efficiently.

#include <iostream>
using namespace std;
void findUnion(int arr1[], int arr2[], int m, int n) {
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])
            cout << arr1[i++] << " ";
        else if (arr2[j] < arr1[i])
            cout << arr2[j++] << " ";
        else {
            cout << arr2[j++] << " ";
            i++;
        }
    }
    while (i < m) cout << arr1[i++] << " ";
    while (j < n) cout << arr2[j++] << " ";
}
void findIntersection(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 {
            cout << arr2[j++] << " ";
            i++;
        }
    }
}
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]);
    cout << "Union: ";
    findUnion(arr1, arr2, m, n);
    cout << "\nIntersection: ";
    findIntersection(arr1, arr2, m, n);
    return 0;
}
            

Output:

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

Method 2: Using Hashing

This method uses a hash table to store unique elements and compute union and intersection.

#include <iostream>
#include <unordered_set>
using namespace std;
void findUnion(int arr1[], int arr2[], int m, int n) {
    unordered_set hash;
    for (int i = 0; i < m; i++) hash.insert(arr1[i]);
    for (int i = 0; i < n; i++) hash.insert(arr2[i]);
    for (auto x : hash) cout << x << " ";
}
void findIntersection(int arr1[], int arr2[], int m, int n) {
    unordered_set hash;
    for (int i = 0; i < m; i++) hash.insert(arr1[i]);
    for (int i = 0; i < n; i++)
        if (hash.find(arr2[i]) != hash.end()) cout << arr2[i] << " ";
}
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]);
    cout << "Union: ";
    findUnion(arr1, arr2, m, n);
    cout << "\nIntersection: ";
    findIntersection(arr1, arr2, m, n);
    return 0;
}
            

Output:

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

Method 3: Using Merge Process

This method merges two arrays into a sorted list and extracts union and intersection.

#iinclude <iostream>
using namespace std;
void mergeUnion(int arr1[], int arr2[], int m, int n) {
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])
            cout << arr1[i++] << " ";
        else if (arr2[j] < arr1[i])
            cout << arr2[j++] << " ";
        else {
            cout << arr2[j++] << " ";
            i++;
        }
    }
    while (i < m) cout << arr1[i++] << " ";
    while (j < n) cout << arr2[j++] << " ";
}
void mergeIntersection(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 {
            cout << arr2[j++] << " ";
            i++;
        }
    }
}
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]);
    cout << "Union: ";
    mergeUnion(arr1, arr2, m, n);
    cout << "\nIntersection: ";
    mergeIntersection(arr1, arr2, m, n);
    return 0;
}
            

Output:

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