The question is to Remove the Minimum Number of Elements Such that No Common Element Exist in both Array.

Given are two arrays, A[] and B[], each with n and m elements. Find the smallest/minimum number of elements to remove from each array so that no common elements exist in both.

Example

Input : A[] = { 5, 2, 5, 5}, B[] = { 5, 3 }
Output : 1
We need to remove 5 from B[]
Input : A[] = { 1, 2, 3, 4, 5}, B[] = {6, 7, 8 }
Output : 0
There is no common element in both.
Input : A[] = { 1, 2, 3, 4, 9}, B[] = { 2, 3, 4, 5, 8, 10 }
Output : 3
2, 3, and 4 need to be removed from any of the two arrays.

Approach

ALGORITHM:

Let's assume that element num is common in both arrays. In array A, num appears x times, and in array B, num appears y times. Therefore, we have three choices for making the intersection of the two arrays null:

Take out every instance of num from array A.

Take away every instance of num from array B.

Now, eliminate every instance of num in both A and B.

Out of these three alternatives, we will select option 1 if x is less than y or option 2 if y is less than x because we must do a minimal amount of operations.

NAIVE APPROACH

The naive approach is to use two for loops and keep the count of the common element and in the end, we remove this common element from the array where the count is less in order to perform the minimal operation. But this will have a greater time complexity, O(n*m) [where n and m are the numbers of elements in array A and array B respectively], since we are using two for loops.

OPTIMAL APPROACH

The best and the optimal approach is to use a hash table to count the instances of each element in the arrays.

We are using two maps, to store the count of the elements of each array.

Map c1 will look something like {1:1, 2:1, 3:1, 4:1, 9:1} and c2 will look something like {2:1, 3:1, 4:1, 5:1, 8:1, 10:1} after counting the frequency of each element of both the arrays.

Now we will run a for loop where we will check the common elements in both the arrays if there are any.

If yes then we will compare their frequency and add the minimum frequency to the “ans” variable.

So in the above example, we can see that 2, 3, and 4 are the common elements in both the arrays.

So we will compare the frequency of each element present in the two arrays and add the minimum frequency to the “ans” variable.

Therefore the ans = 3. (freq of 2 + freq of 3 + freq of 4)

C++ CODE

/*Remove the Minimum Number of Elements Such that No Common Element Exist in both Array*/
#include <bits/stdc++.h>
using namespace std;
int MinElementsRemove(vector<int> &arr, vector<int> &brr)
{
unordered_map<int, int> c1, c2;
for (auto i : arr)
{
c1[i]++;
}
for (auto i : brr)
{
c2[i]++;
}
int ans = 0;
for (auto i : c1)
{
if (c2.count(i.first) == 1)
{
ans += min(c2[i.first], c1[i.first]);
}
}
return ans;
}
int main()
{
vector<int> arr = {1, 2, 3, 4, 9};
vector<int> brr = {2, 3, 4, 5, 8, 10};
cout << "Minimum number of elements that we need to remove such that no common elements exist in both array: " << MinElementsRemove(arr, brr) << endl;
return 0;
}

OUTPUT

Minimum number of elements that we need to remove such that no common elements exist in both array: 3

JAVA CODE

/*Remove the Minimum Number of Elements Such that No Common Element Exist in both Array*/
import java.util.*;
public class Main
{
public static int MinElementsRemove(int[] arr, int[] brr)
{
Map<Integer, Integer> c1 = new HashMap<Integer, Integer>();
Map<Integer, Integer> c2 = new HashMap<Integer, Integer>();
for (int i=0; i<arr.length; i++)
{
Integer j = c1.get(arr[i]);
c1.put(arr[i], (j == null) ? 1 : j + 1);
}
for (int i=0; i<brr.length; i++)
{
Integer j =c2.get(brr[i]);
c2.put(brr[i], (j == null) ? 1 : j + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : c1.entrySet()){
if (c2.get(entry.getKey()) != null)
{
ans += Math.min(c2.get(entry.getKey()), c1.get(entry.getKey()));
}
}
return ans;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 9};
int[] brr = {2, 3, 4, 5, 8, 10};
System.out.println("Minimum number of elements that we need to remove such that no common elements exist in both array: " + MinElementsRemove(arr, brr));
}
}

OUTPUT

Minimum number of elements that we need to remove such that no common elements exist in both array: 3

PYTHON CODE

#Remove the Minimum Number of Elements Such that No Common Element Exist in both Array
def minRemove(arr, brr, n, m):
c1 = dict()
c2 = dict()
# Count elements of arr
for i in range(n):
c1[arr[i]] = c1.get(arr[i], 0) + 1
# Count elements of brr
for i in range(m):
c2[brr[i]] = c2.get(brr[i], 0) + 1
ans = 0
for x in c1:
if x in c2.keys():
ans += min(c1[x],c2[x])
return ans
# Driver Code
a = [1, 2, 3, 4, 9]
b = [2, 3, 4, 5, 8, 10]
n = len(a)
m = len(b)
print(minRemove(a, b, n, m))

OUTPUT

3

Time Complexity

The total time complexity for the above approach is O(N+M) because we iterate over each array once. (where n and m are the numbers of elements in array A and array B respectively).

Space Complexity

The frequency of items for both arrays was stored using two hash tables. Hence the space complexity is O(N+M). (where n and m are the numbers of elements in array A and array B respectively).

Key/value pairs are kept in a data structure called a hash table. To determine the index into an array where an element will be inserted or searched, it uses a hash function.

Can Hashtable have duplicate keys?

Hashtables can only contain unique keys by design. Therefore duplicate keys cannot be added to them.

What is the load factor of a hash table?

The definition of a load factor is (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased and n is the overall size of the hash table.

What is the time complexity of the above approach to solve the question?

The time complexity of the above approach where the hash map has been used is O(n+m).

What will be the space complexity of the above approach to solve the question?

The space complexity of the above approach where the hash map has been used is O(m+n).

Conclusion

In this article, we have extensively discussed the problem of, Remove the Minimum Number of Elements Such that No Common Element Exist in both Array. We hope this blog has helped you understand this sum.