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.

def find_union(arr1, arr2):
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            print(arr1[i], end=" ")
            i += 1
        elif arr2[j] < arr1[i]:
            print(arr2[j], end=" ")
            j += 1
        else:
            print(arr2[j], end=" ")
            i += 1
            j += 1
    while i < len(arr1):
        print(arr1[i], end=" ")
        i += 1
    while j < len(arr2):
        print(arr2[j], end=" ")
        j += 1

def find_intersection(arr1, arr2):
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            i += 1
        elif arr2[j] < arr1[i]:
            j += 1
        else:
            print(arr2[j], end=" ")
            i += 1
            j += 1

arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
print("Union:", end=" ")
find_union(arr1, arr2)
print("\nIntersection:", end=" ")
find_intersection(arr1, arr2)
            

Output:

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

Method 2: Using Set

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

def find_union(arr1, arr2):
    print(" ".join(map(str, sorted(set(arr1) | set(arr2)))))

def find_intersection(arr1, arr2):
    print(" ".join(map(str, sorted(set(arr1) & set(arr2)))))

arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
print("Union:", end=" ")
find_union(arr1, arr2)
print("\nIntersection:", end=" ")
find_intersection(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.

def merge_union(arr1, arr2):
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            print(arr1[i], end=" ")
            i += 1
        elif arr2[j] < arr1[i]:
            print(arr2[j], end=" ")
            j += 1
        else:
            print(arr2[j], end=" ")
            i += 1
            j += 1
    while i < len(arr1):
        print(arr1[i], end=" ")
        i += 1
    while j < len(arr2):
        print(arr2[j], end=" ")
        j += 1

def merge_intersection(arr1, arr2):
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            i += 1
        elif arr2[j] < arr1[i]:
            j += 1
        else:
            print(arr2[j], end=" ")
            i += 1
            j += 1

arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
print("Union:", end=" ")
merge_union(arr1, arr2)
print("\nIntersection:", end=" ")
merge_intersection(arr1, arr2)
            

Output:

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