Union and Intersection of Two Sorted Arrays

Introduction

• Focus on Union and Intersection of two sorted arrays.
• Sorted arrays are defined as being in ascending order.

Definitions

Union

• Union of two sets A and B includes all elements that are in A, B, or both.
• Example: For arrays 1 and 2, the union consists of all unique elements from both arrays.

Intersection

• Intersection includes the common elements between the two arrays.
• Example: For arrays 1 and 2, the intersection consists of elements present in both arrays (e.g., 3 and 5).

Algorithm for Union

1. Initialize two index variables I and J to zero.
2. Compare elements at I in array 1 and J in array 2:
   • If element at I is smaller, add it to the union and increment I.
   • If element at J is smaller, add it to the union and increment J.
   • If both elements are equal, add one of them to the union and increment both I and J.
3. Once one array is exhausted, add remaining elements from the other array.

Example Walkthrough for Union

• Given Array 1: [1, 3, 4, 5, 7]
  Given Array 2: [2, 3, 5, 6]
  • Iteration Steps:
    • Compare 1 and 2: Add 1, increment I.
    • Compare 3 and 2: Add 2, increment J.
    • Compare 3 and 3: Add 3, increment both I and J.
    • Compare 4 and 5: Add 4, increment I.
    • Compare 5 and 5: Add 5, increment both I and J.
    • Compare 7 and 6: Add 6, increment J.
    • Add remaining from Array 1: Resulting Union = [1, 2, 3, 4, 5, 6, 7].

Time Complexity for Union

• Time complexity is O(M + N) where M and N are the sizes of the two arrays.

Algorithm for Intersection

1. Initialize I and J to zero.
2. Compare elements at I in array 1 and J in array 2:
   • If elements are equal, add to intersection and increment both I and J.
   • If element at I is smaller, increment I.
   • If element at J is smaller, increment J.
3. Stop when one array is exhausted.

Example Walkthrough for Intersection

• Given Array 1: [1, 3, 4, 5, 7]
  Given Array 2: [2, 3, 5, 6]
  • Iteration Steps:
    • Compare 1 and 2: Increment I.
    • Compare 3 and 2: Increment J.
    • Compare 3 and 3: Add 3, increment both.
    • Compare 4 and 5: Increment I.
    • Compare 5 and 5: Add 5, increment both.
    • Finish as Array 2 is exhausted.
    • Resulting Intersection = [3, 5].

Time Complexity for Intersection

• Time complexity is also O(M + N).

Conclusion

• The algorithms for union and intersection of two sorted arrays are efficient and straightforward.
• Both algorithms run in linear time relative to the input sizes.
• Additional resources can be found on Geeks for Geeks.