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.

import java.util.*;
class UnionIntersection {
    static void findUnion(int arr1[], int arr2[]) {
        int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j])
                System.out.print(arr1[i++] + " ");
            else if (arr2[j] < arr1[i])
                System.out.print(arr2[j++] + " ");
            else {
                System.out.print(arr2[j++] + " ");
                i++;
            }
        }
        while (i < arr1.length) System.out.print(arr1[i++] + " ");
        while (j < arr2.length) System.out.print(arr2[j++] + " ");
    }
    static void findIntersection(int arr1[], int arr2[]) {
        int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) i++;
            else if (arr2[j] < arr1[i]) j++;
            else {
                System.out.print(arr2[j++] + " ");
                i++;
            }
        }
    }
    public static void main(String args[]) {
        int arr1[] = {1, 2, 4, 5, 6};
        int arr2[] = {2, 3, 5, 7};
        System.out.print("Union: ");
        findUnion(arr1, arr2);
        System.out.print("\nIntersection: ");
        findIntersection(arr1, arr2);
    }
}
            

Output:

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

Method 2: Using HashSet

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

import java.util.*;
class HashSetUnionIntersection {
    static void findUnion(int arr1[], int arr2[]) {
        Set set = new HashSet<>();
        for (int num : arr1) set.add(num);
        for (int num : arr2) set.add(num);
        for (int num : set) System.out.print(num + " ");
    }
    static void findIntersection(int arr1[], int arr2[]) {
        Set set = new HashSet<>();
        for (int num : arr1) set.add(num);
        for (int num : arr2) {
            if (set.contains(num)) System.out.print(num + " ");
        }
    }
    public static void main(String args[]) {
        int arr1[] = {1, 2, 4, 5, 6};
        int arr2[] = {2, 3, 5, 7};
        System.out.print("Union: ");
        findUnion(arr1, arr2);
        System.out.print("\nIntersection: ");
        findIntersection(arr1, arr2);
    }
}
            

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.

import java.util.*;
class MergeUnionIntersection {
    static void mergeUnion(int arr1[], int arr2[]) {
        int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j])
                System.out.print(arr1[i++] + " ");
            else if (arr2[j] < arr1[i])
                System.out.print(arr2[j++] + " ");
            else {
                System.out.print(arr2[j++] + " ");
                i++;
            }
        }
        while (i < arr1.length) System.out.print(arr1[i++] + " ");
        while (j < arr2.length) System.out.print(arr2[j++] + " ");
    }
    static void mergeIntersection(int arr1[], int arr2[]) {
        int i = 0, j = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) i++;
            else if (arr2[j] < arr1[i]) j++;
            else {
                System.out.print(arr2[j++] + " ");
                i++;
            }
        }
    }
    public static void main(String args[]) {
        int arr1[] = {1, 2, 4, 5, 6};
        int arr2[] = {2, 3, 5, 7};
        System.out.print("Union: ");
        mergeUnion(arr1, arr2);
        System.out.print("\nIntersection: ");
        mergeIntersection(arr1, arr2);
    }
}
            

Output:

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