Union of Arrays with Duplicates

Given two arrays a[] and b[],the task is to find the number of elements in the union between these two arrays.

The Union of the two arrays can be defined as the set containing distinct elements from both arrays. If there are repetitions, then only one element occurrence should be there in the union.

Note:Elements of a[] and b[] are not necessarily distinct.

Examples

Input: a[] = [1, 2, 3, 4, 5], b[] = [1, 2, 3]
Output: 5
Explanation: Union set of both the arrays will be 1, 2, 3, 4 and 5. So count is 5.

Input: a[] = [85, 25, 1, 32, 54, 6], b[] = [85, 2] 
Output: 7
Explanation: Union set of both the arrays will be 85, 25, 1, 32, 54, 6, and 2. So count is 7.

Input: a[] = [1, 2, 1, 1, 2], b[] = [2, 2, 1, 2, 1] 
Output: 2
Explanation: We need to consider only distinct. So count of elements in union set will be 2.

Constraints:
1 ≤ a.size(), b.size() ≤ 10⁶
0 ≤ a[i], b[i] ≤ 10⁵

Approach 01:

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    // Function to return the count of number of elements in the union of two arrays
    int findUnion(vector<int>& arrayA, vector<int>& arrayB) {
        unordered_set<int> uniqueElements;
        
        // Add elements from the first array to the set
        for (int element : arrayA) {
            uniqueElements.insert(element);
        }

        // Add elements from the second array to the set
        for (int element : arrayB) {
            uniqueElements.insert(element);
        }

        // Return the number of unique elements
        return uniqueElements.size();
    }
};

class Solution:
    # Function to return the count of number of elements in the union of two arrays
    def findUnion(self, arrayA, arrayB):
        uniqueElements = set()
        
        # Add elements from the first array to the set
        for element in arrayA:
            uniqueElements.add(element)
        
        # Add elements from the second array to the set
        for element in arrayB:
            uniqueElements.add(element)
        
        # Return the number of unique elements
        return len(uniqueElements)

Time Complexity

• Inserting Elements into Set:
  • Inserting an element into an unordered set takes average \( O(1) \) time, but in the worst case (when a hash collision occurs), it could take \( O(n) \). However, in practice, the average case is \( O(1) \). Hence, the insertion of all elements from both arrays takes:
    \( O(n + m) \), where \( n \) and \( m \) are the sizes of arrayA and arrayB, respectively.
• Overall Time Complexity:

  The total time complexity is:
  \( O(n + m) \), where \( n \) is the length of arrayA and \( m \) is the length of arrayB.

Space Complexity

• Storage for Unordered Set:
  • We store each unique element from both arrays in an unordered set. In the worst case, all elements in the arrays are unique, resulting in a space complexity of: \( O(n + m) \), where \( n \) and \( m \) are the sizes of arrayA and arrayB.
• Overall Space Complexity:

  The total space complexity is: \( O(n + m) \), where \( n \) is the length of arrayA and \( m \) is the length of arrayB.