Remove the Minimum Number of Elements Such that No Common Element Exist in both Array

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:

1. Take out every instance of num from array A.
2. Take away every instance of num from array B.
3. 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.

Let's understand it step-wise through an example.

Let the two arrays be:

arr[] = {1, 2, 3, 4, 9}
brr[] = {2, 3, 4, 5, 8, 10}

1. We are using two maps, to store the count of the elements of each array.
2. 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.
3. Now we will run a for loop where we will check the common elements in both the arrays if there are any.
4. If yes then we will compare their frequency and add the minimum frequency to the “ans” variable.
5. So in the above example, we can see that 2, 3, and 4 are the common elements in both the arrays.
6. 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).

You can also read about the Longest Consecutive Sequence.

Frequently Asked  Questions

What can be done with a hash table?

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.

If you want to learn more, check out our articles on Distribute maximum number of chocolates amongst X students, Winner of Tic-tac-toe, Reduce Array Size to The half, and Minimum number of subsets with distinct elements.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!