Union of Two Sorted Arrays with Distinct Elements

Given two sorted arrays a[] and b[], where each array contains distinct elements , the task is to return the elements in the union of the two arrays in sorted order.

Union of two arrays can be defined as the set containing distinct common elements that are present in either of the arrays.

Examples:

Input: a[] = [1, 2, 3, 4, 5], b[] = [1, 2, 3, 6, 7]
Output: 1 2 3 4 5 6 7
Explanation: Distinct elements including both the arrays are: 1 2 3 4 5 6 7.

Input: a[] = [2, 3, 4, 5], b[] = [1, 2, 3, 4]
Output: 1 2 3 4 5
Explanation: Distinct elements including both the arrays are: 1 2 3 4 5.

Input: a[] = [1], b[] = [2]
Output: 1 2
Explanation: Distinct elements including both the arrays are: 1 2.

Constraints:
1 <= a.size(), b.size() <= 10⁵
-10⁹ <= a[i] , b[i] <= 10⁹

Approach 01:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to return a vector containing the union of the two arrays.
    vector<int> findUnion(vector<int> &firstArray, vector<int> &secondArray) {
        // Convert arrays to sets to remove duplicates
        set<int> firstSet(firstArray.begin(), firstArray.end());
        set<int> secondSet(secondArray.begin(), secondArray.end());

        // Take the union of both sets and store in a vector
        vector<int> unionResult(firstSet.begin(), firstSet.end());
        unionResult.insert(unionResult.end(), secondSet.begin(), secondSet.end());

        // Remove duplicates and sort the result
        set<int> finalSet(unionResult.begin(), unionResult.end());
        unionResult.assign(finalSet.begin(), finalSet.end());

        return unionResult;
    }
};

class Solution:
    # Function to return a list containing the union of the two arrays.
    def findUnion(self, firstArray, secondArray):
        # Convert the arrays to sets to remove duplicates
        firstSet = set(firstArray)
        secondSet = set(secondArray)
        
        # Take the union of the two sets, convert it to a sorted list
        unionResult = list(firstSet | secondSet)
        unionResult.sort()
        return unionResult

Time Complexity

• Converting Arrays to Sets:

  Creating a set from firstArray and secondArray takes \( O(n \log n) \) and \( O(m \log m) \) time, where \( n \) and \( m \) are the sizes of the two arrays.

• Inserting Elements into the Result Vector:

  Inserting elements from both sets into the unionResult vector takes \( O(n + m) \) time.

• Removing Duplicates and Sorting:

  Inserting all elements into a final set to remove duplicates and sorting takes \( O((n + m) \log(n + m)) \) time.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting and set operations: \( O((n + m) \log(n + m)) \).

Space Complexity

• Auxiliary Data Structures:

  We use three sets (firstSet, secondSet, and finalSet) and a vector unionResult. In the worst case, each set can contain up to \( n + m \) elements.

• Overall Space Complexity:

  The space complexity is \( O(n + m) \) due to the sets and the result vector used to store the union.