30. Union of Two Arrays with Duplicates

The problem can be found at the following link: Problem Link

Problem Description

You are given two arrays a[] and b[]. The task is to find the number of distinct elements in the union of the two arrays.

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

Examples

Input: a[] = [1, 2, 3, 4, 5] b[] = [1, 2, 3] Output: 5 Explanation: The union set of both arrays is {1, 2, 3, 4, 5}. The count of distinct elements is 5.

Input: a[] = [85, 25, 1, 32, 54, 6] b[] = [85, 2] Output: 7 Explanation: The union set of both arrays is {85, 25, 1, 32, 54, 6, 2}. The count of distinct elements is 7.

Input: a[] = [1, 2, 1, 1, 2] b[] = [2, 2, 1, 2, 1] Output: 2 Explanation: The union set of both arrays is {1, 2}. The count of distinct elements is 2.

Constraints

• $1 ≤ a.size(), b.size() ≤ 10^6$

• $0 ≤ a[i], b[i] ≤ 10^5$

My Approach

Efficient Approach Using Hashing

1. Key Idea: Use a hash set to automatically store unique elements from both arrays.

2. Steps:

   • Insert all elements from the first array a[] into the hash set.

   • Insert all elements from the second array b[] into the hash set.

   • The size of the hash set gives the total number of distinct elements in the union.

3. This approach is efficient because:

   • Insertion into a hash set is O(1) on average.

   • By directly storing unique elements, the problem of duplicates is handled efficiently.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(a.size() + b.size())

  • Traversing each array once and inserting into the hash set takes linear time proportional to the size of the arrays.

• Expected Auxiliary Space Complexity: O(a.size() + b.size())

  • The hash set can hold up to a.size() + b.size() distinct elements in the worst case.

Code (C++)

class Solution {
public:
    int findUnion(vector<int>& a, vector<int>& b) {
        unordered_set<int> s(a.begin(), a.end());
        s.insert(b.begin(), b.end());
        return s.size();
    }
};

Code (Java)

class Solution {
    public static int findUnion(int[] a, int[] b) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : a) set.add(num);
        for (int num : b) set.add(num);
        return set.size();
    }
}

Code (Python)

class Solution:
    def findUnion(self, a, b):
        return len(set(a).union(b))

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count