Find the Union and Intersection of the two sorted arrays

To Find the union and intersection of two sorted arrays is a common problem in programming, particularly when dealing with sets of elements. The union of two sets represents the combined elements from both sets, while the intersection represents the elements that are common to both sets.

The approach used in the provided example takes advantage of the fact that the arrays are sorted, allowing for an efficient solution. By comparing elements from both arrays, the algorithm determines the union and intersection by iterating through the arrays simultaneously.

Find the Union and Intersection of the two sorted arrays

To find the union and intersection of two sorted arrays, you can use a simple approach that leverages the sorted nature of the arrays. Here’s an example implementation in Java:


import java.util.ArrayList;
import java.util.List;

public class UnionIntersection {
    
    public static List<Integer> findUnion(int[] arr1, int[] arr2) {
        List<Integer> union = new ArrayList<>();
        int i = 0, j = 0;
        int n = arr1.length, m = arr2.length;

        while (i < n && j < m) {
            if (arr1[i] < arr2[j]) {
                union.add(arr1[i]);
                i++;
            } else if (arr1[i] > arr2[j]) {
                union.add(arr2[j]);
                j++;
            } else {
                union.add(arr1[i]);
                i++;
                j++;
            }
        }

        // Add remaining elements from arr1, if any
        while (i < n) {
            union.add(arr1[i]);
            i++;
        }

        // Add remaining elements from arr2, if any
        while (j < m) {
            union.add(arr2[j]);
            j++;
        }

        return union;
    }

    public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
        List<Integer> intersection = new ArrayList<>();
        int i = 0, j = 0;
        int n = arr1.length, m = arr2.length;

        while (i < n && j < m) {
            if (arr1[i] < arr2[j]) {
                i++;
            } else if (arr1[i] > arr2[j]) {
                j++;
            } else {
                intersection.add(arr1[i]);
                i++;
                j++;
            }
        }

        return intersection;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 4, 5, 7};
        int[] arr2 = {2, 3, 5, 6};

        List<Integer> union = findUnion(arr1, arr2);
        System.out.println("Union: " + union);

        List<Integer> intersection = findIntersection(arr1, arr2);
        System.out.println("Intersection: " + intersection);
    }
}

Output:


Union: [1, 2, 3, 4, 5, 6, 7]
Intersection: [3, 5]

Let’s go through the code step by step:

The findUnion method takes two sorted integer arrays, arr1 and arr2, as input, and returns a list containing the union of the two arrays.
We initialize an empty list called union to store the elements of the union.
We use two pointers, i and j, to traverse arr1 and arr2 respectively.
While both pointers are within the bounds of their respective arrays, we compare the elements at the current positions of the pointers.
If the element in arr1 is less than the element in arr2, we add the element from arr1 to the union list and increment i.
If the element in arr1 is greater than the element in arr2, we add the element from arr2 to the union list and increment j.
If the elements are equal, we add the element to the union list and increment both pointers.
After the loop, if there are any remaining elements in arr1, we add them to the union list.
Similarly, if there are any remaining elements in arr2, we add them to the union list.
The findIntersection method is similar to findUnion, but instead of adding elements to the union list, it adds them to the intersection list when the elements are equal.
In the main method, we create two example arrays, arr1 and arr2, and call the findUnion and findIntersection methods.
We then print the resulting union and intersection lists.

Time Complexity and Storage:

The time complexity of finding the union and intersection is O(n + m), where n and m are the lengths of the input arrays. This is because the algorithm performs a single pass through both arrays, comparing and processing each element once. The complexity is linear and directly proportional to the total number of elements in the arrays.

The space complexity of the example is O(k), where k represents the number of elements in the union or intersection. In the worst case, where there are no common elements, the size of the union is n + m, resulting in a space complexity of O(n + m). However, if the arrays have many common elements, the size of the intersection will be smaller, resulting in a lower space complexity.

Overall, the provided solution offers an efficient way to find the union and intersection of two sorted arrays, with a time complexity of O(n + m) and a space complexity of O(k).