Merge 2 Sorted Array

The solution to the problem can be to store all the elements of array ‘A’ and array ‘B’ in a set.

This way, all the elements of array ‘A’ and array ‘B’ will be included in the set. 

Also, one number will not be present more than once (because we are using a set). 

In the end, we can take all the elements of the set and store them in a ‘dynamic array’, then we can return it.

The steps are as follows:-

// Function to find the union of two sorted arrays

            function sortedArray(int[] A, int[] B, int N, int M):
 

1. Int 'N', and ‘M’ be the size of arrays ‘A’ and ‘B’, respectively.
2. Initialize a set ‘st’ of type ‘int’.
3. Iterate over array ‘A’ and insert elements into set ‘st’.
4. Iterate over array ‘B’ and insert elements into set ‘st’.
5. Initialize a 1-D array ‘unionArray’.
6. Iterate over the set and insert elements into the array unionArray.
7. Return unionArray.

The solution to the problem can be to use two pointers, ‘i' and ‘j’, pointing to the 0th index of arrays ‘A’ and ‘B’, respectively. We will create an empty dynamic array to store the union of arrays ‘A’ and ‘B’. Using the pointers ‘i’ and ‘j’, we will traverse the respective arrays and insert distinct elements from ‘A’ and ‘B’ into the ‘unionArray’ dynamic array in ascending order.
 

While traversing, we may encounter the following three cases:

1. A[i] = B[j]
   Here, we have found a common element, so we will insert only one element in the ‘unionArray’ dynamic array. Suppose we insert A[i] in the ‘unionArray’ dynamic array and increment ‘i’.
   
   There can be a scenario where the element we will insert is already present in the ‘unionArray’ dynamic array. If we didn’t apply any kind of checks/conditions, it might be possible that duplicates will be present in ‘unionArray’. One way to deal with this is to check for the last ( latest ) element inserted in ‘unionArray’ and compare it with the element we want to insert now. If they are the same, we may skip inserting this element; otherwise, we can insert it into the dynamic array.
    
2. A[i] < B[j]
   Since A[i] is smaller, we may insert it into ‘unionArray’ if and only if the last element in ‘unionArray’ is not equal to A[i]. Whether it is inserted in ‘unionArray’ or not, we will increment ‘i’.
    
3. A[i] > B[j]
   Since B[j] is smaller, we may insert it into ‘unionArray’ if and only if the last element in ‘unionArray’ is not equal to B[j]. Whether it is inserted in ‘unionArray’ or not, we will increment ‘j’.

After traversing, if any elements are left in ‘A’ or ‘B’ which are not traversed, then check for conditions and, based on that, insert them into ‘unionArray’.
 

The steps are as follows:-

// Function to find the union of two sorted arrays

            function sortedArray(int[] A, int[] B, int N, int M):
 

1. Int 'N', and ‘M’ be the size of arrays ‘A’ and ‘B’, respectively.
2. Initialize a 1-D array ‘unionArray’.
3. while ‘i < N and j < M’:
   • if A[i] <= B[j]:
     • if ‘unionArray.size()’ == 0 OR ‘unionArray.back()’ != A[i]:
       • Insert A[i] in ‘unionArray’
     • Increment ‘i’
   • if A[i] > B[j]:
     • If ‘unionArray.size()’ == 0 OR ‘unionArray.back()’ != B[j]:
       • Insert B[j] in ‘unionArray’
     • Increment ‘j’
4. While ‘i < N’:
   • if ‘unionArray.back()’ != A[i]:
     • Insert A[i] in ‘unionArray’
   • Increment ‘i’
5. while ‘j < M’:
   • if ‘unionArray.back()’ != B[j]:
     • Insert B[j] in ‘unionArray’
   • Increment ‘j’
6. Return ‘unionArray’