Union of Two Sorted Arrays

Finding the union of two sorted arrays involves combining the elements of both arrays without duplicates. This problem can be solved using different approaches, each with its own time and space complexity. In this article, we'll discuss two approaches to achieve this union.

Solution 1: Brute Force Approach (using Set)

This method involves using a set to store the unique elements from both arrays, ensuring that duplicates are removed.

Implementation:

// Solution-1: Brute Force Approach (Using Set)
// Time Complexity: O((m+n)log(m+n))
// Space Complexity: O(m+n)
// {If Space of temp Array is considered}
// Space Complexity: O(1)
// {If Space of temp Array is Not considered}
vector<int> unionOfSortedArrays1(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    set<int> uniqueElements;

    for (int i = 0; i < n; i++)
    {
        uniqueElements.insert(arr1[i]);
    }

    for (int i = 0; i < m; i++)
    {
        uniqueElements.insert(arr2[i]);
    }

    vector<int> temp;

    for (auto it : uniqueElements)
    {
        temp.push_back(it);
    }

    return temp;
}

Logic:

1. Insert Elements into Set: Insert all elements of both arrays into a set to remove duplicates.

2. Copy to Vector: Copy elements from the set back to a temporary vector.

Time Complexity: O((m+n) log(m+n))

• Explanation: Inserting each element from arr1 and arr2 into the set uniqueElements takes O(log k) time, where k is the number of elements in the set. As we insert a total of m + n elements, this results in O((m+n) log(m+n)) time complexity. After inserting all elements, copying the set elements back to a vector takes O(m+n) time.

Space Complexity: O(m+n)

• Explanation: The set uniqueElements can contain up to m + n elements in the worst case where there are no duplicates. Additionally, the temporary vector temp also stores up to m + n elements. If we consider the space required for the set and the temporary vector, the space complexity is O(m+n).

  If we do not consider the temporary vector, the space complexity is O(1) as we are only using the set for extra storage.

Example:

• Input: arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], n = 10, arr2 = [2, 3, 4, 4, 5, 11, 12], m = 7

• Output: union = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

• Explanation: Elements from both arrays are combined without duplicates.

---

Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses two pointers to efficiently merge the arrays while avoiding duplicates.

Implementation:

// Solution-2: Optimal Approach (Using 2 Pointers)
// Time Complexity: O(m+n)
// Space Complexity: O(m+n)
// {If Space of temp Array is considered}
// Space Complexity: O(1)
// {If Space of temp Array is Not considered}
vector<int> unionOfSortedArrays2(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    int i = 0;
    int j = 0;

    vector<int> temp;

    while (i < n && j < m)
    {
        if (arr1[i] <= arr2[j])
        {
            if (temp.size() == 0 || arr1[i] != temp.back()) // Avoid duplicates
            {
                temp.push_back(arr1[i]);
            }
            i++;
        }
        else
        {
            if (temp.size() == 0 || arr2[j] != temp.back()) // Avoid duplicates
            {
                temp.push_back(arr2[j]);
            }
            j++;
        }
    }

    // Handle remaining elements in 'arr1' (if any)
    while (i < n)
    {
        if (arr1[i] != temp.back())
        {
            temp.push_back(arr1[i]);
        }
        i++;
    }

    // Handle remaining elements in 'arr2' (if any)
    while (j < m)
    {
        if (arr2[j] != temp.back())
        {
            temp.push_back(arr2[j]);
        }
        j++;
    }

    return temp;
}

Logic:

1. Initialize Pointers: Use two pointers, one for each array.

2. Compare Elements: Compare elements at both pointers and add the smaller one to the result if it's not a duplicate.

3. Advance Pointers: Move the pointer forward for the array from which the element was taken.

4. Handle Remaining Elements: Add any remaining elements from either array.

Time Complexity: O(m+n)

• Explanation: In the worst case, each element in both arrays is processed exactly once, resulting in O(m+n) time complexity.

Space Complexity: O(m+n)

• Explanation: The temporary vector temp stores the union of elements from both arrays. In the worst case where there are no duplicates, temp will contain m + n elements. Therefore, the space complexity is O(m+n) considering the temporary vector.

  If we do not consider the space for the temporary vector, the space complexity is O(1) as we are only using a constant amount of extra space for variables i and j.

Example:

• Input: arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], n = 10, arr2 = [2, 3, 4, 4, 5, 11, 12], m = 7

• Output: union = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

• Explanation: Elements from both arrays are merged without duplicates.

---

Comparison

• Brute Force Method (Using Set):

  • Pros: Simple and straightforward.
  • Cons: Less efficient for large arrays due to O((m+n) log(m+n)) time complexity.

• Optimal Method (Using Two Pointers):

  • Pros: Efficient with O(m+n) time complexity.
  • Cons: Slightly more complex to implement but highly efficient for large arrays.

Edge Cases

• Empty Arrays: Returns an empty array.

• No Common Elements: Returns all elements from both arrays.

• All Elements Common: Returns the common elements without duplicates.

Additional Notes

• Efficiency: The two-pointers method is more time-efficient.

• Practicality: The choice between methods depends on the specific constraints and requirements of the problem.

Conclusion

Finding the union of two sorted arrays can be efficiently achieved using either a set or a two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.

---