Intersection of Two arrays with Duplicate Elements

Given two integer arrays a[] and b[], you have to find the intersection of the two arrays. Intersection of two arrays is said to be elements that are common in both arrays. The intersection should not have duplicate elements and the result should contain items in any order.

Note:The driver code will sort the resulting array in increasing order before printing.

Examples:

Input: a[] = [1, 2, 1, 3, 1], b[] = [3, 1, 3, 4, 1]
Output: [1, 3]
Explanation: 1 and 3 are the only common elements and we need to print only one occurrence of common elements.

Input: a[] = [1, 1, 1], b[] = [1, 1, 1, 1, 1]
Output: [1]
Explanation: 1 is the only common element present in both the arrays.

Input: a[] = [1, 2, 3], b[] = [4, 5, 6]
Output: []
Explanation: No common element in both the arrays.

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

Approach 01:

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

class Solution {
public:
    vector<int> intersectionWithDuplicates(vector<int>& arrayA, vector<int>& arrayB) {
        set<int> uniqueElementsA;
        set<int> uniqueElementsB;
        vector<int> intersectionResult;

        // Insert elements of arrayA into uniqueElementsA
        for (int element : arrayA) {
            uniqueElementsA.insert(element);
        }

        // Insert elements of arrayB into uniqueElementsB
        for (int element : arrayB) {
            uniqueElementsB.insert(element);
        }

        // Find common elements between the two sets
        for (const int& element : uniqueElementsA) {
            if (uniqueElementsB.find(element) != uniqueElementsB.end()) {
                intersectionResult.push_back(element);
            }
        }

        return intersectionResult;
    }
};

class Solution:
    def intersectionWithDuplicates(self, arrayA, arrayB):
        uniqueElementsA = set()
        uniqueElementsB = set()
        intersectionResult = []

        # Insert elements of arrayA into uniqueElementsA
        for element in arrayA:
            uniqueElementsA.add(element)

        # Insert elements of arrayB into uniqueElementsB
        for element in arrayB:
            uniqueElementsB.add(element)

        # Find common elements between the two sets
        for element in uniqueElementsA:
            if element in uniqueElementsB:
                intersectionResult.append(element)

        return intersectionResult

Time Complexity

• Inserting into Sets:
  • Inserting each element of arrayA into uniqueElementsA takes \( O(n_a \log n_a) \), where \( n_a \) is the size of arrayA.
  • Inserting each element of arrayB into uniqueElementsB takes \( O(n_b \log n_b) \), where \( n_b \) is the size of arrayB.
• Finding Intersection:
  • Iterating through uniqueElementsA and checking for existence in uniqueElementsB takes \( O(n_a \log n_b) \), as each lookup in a set takes \( O(\log n_b) \).
• Overall Time Complexity:

  The total time complexity is: \( O(n_a \log n_a + n_b \log n_b + n_a \log n_b) \).

Space Complexity

• Sets:
  • The space required to store elements in uniqueElementsA is \( O(n_a) \).
  • The space required to store elements in uniqueElementsB is \( O(n_b) \).
• Result Vector:
  • The space required for the intersectionResult vector depends on the number of common elements, which can be at most \( O(\min(n_a, n_b)) \).
• Auxiliary Variables:
  • Additional variables for iteration and intermediate storage require \( O(1) \) space.
• Overall Space Complexity:

  The total space complexity is: \( O(n_a + n_b) \).