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 <stdio.h>
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])
            printf("%d ", arr1[i++]);
        else if (arr2[j] < arr1[i])
            printf("%d ", arr2[j++]);
        else {
            printf("%d ", arr2[j++]);
            i++;
        }
    }
    while (i < m) printf("%d ", arr1[i++]);
    while (j < n) printf("%d ", 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 {
            printf("%d ", 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]);
    printf("Union: ");
    findUnion(arr1, arr2, m, n);
    printf("\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 <stdio.h>
#include <stdlib.h>
#define MAX 1000
int hash[MAX] = {0};
void findUnion(int arr1[], int arr2[], int m, int n) {
    for (int i = 0; i < m; i++) hash[arr1[i]] = 1;
    for (int i = 0; i < n; i++) hash[arr2[i]] = 1;
    for (int i = 0; i < MAX; i++)
        if (hash[i]) printf("%d ", i);
}
void findIntersection(int arr1[], int arr2[], int m, int n) {
    for (int i = 0; i < m; i++) hash[arr1[i]] = 1;
    for (int i = 0; i < n; i++)
        if (hash[arr2[i]]) printf("%d ", 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]);
    printf("Union: ");
    findUnion(arr1, arr2, m, n);
    printf("\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.

#include <stdio.h>
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])
            printf("%d ", arr1[i++]);
        else if (arr2[j] < arr1[i])
            printf("%d ", arr2[j++]);
        else {
            printf("%d ", arr2[j++]);
            i++;
        }
    }
    while (i < m) printf("%d ", arr1[i++]);
    while (j < n) printf("%d ", 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 {
            printf("%d ", 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]);
    printf("Union: ");
    mergeUnion(arr1, arr2, m, n);
    printf("\nIntersection: ");
    mergeIntersection(arr1, arr2, m, n);
    return 0;
}
            

Output:

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