Remove Minimum Number of Elements Such That no Common Element Exist in both Array


Difficulty Level Easy
Frequently asked in Alation MetLife Oxigen Wallet ServiceNow Spotify
Array Hash

Given two arrays A and B consisting of n and m elements respectively. Remove minimum number of elements such that no common element exist in both array and print the count of elements which removed.

Example

Input:

A[]={ 1, 2, 1, 1}

B[]= {1, 1}

Output:

Minimum elements to remove from each array are 3.

Main idea

Let’s say we have an element num which is common in both the arrays. Num appears X number of times in array A and Y number of times in array B. So to make the intersection of the two arrays null, we have three options:

  1. Remove all the occurrences of num from array A.
  2. Remove all the occurrences of num from array B.
  3. Now, Remove all the occurrences of num from both A and B.

As we have to do a minimum number of operations, out of these three options, we will choose 1st option if X is less than Y, or 2nd option if Y is less than X.

To count the occurrences of each element in the arrays, we will use the hash table.

Algorithm for Remove minimum number of elements

  1. Initialize a variable ans which will store the answer.
  2. Iterate over the arrays and store the occurrence of every element in a hash table for both arrays.
  3. For each element num in the arrays, if X is the number of occurrence of num in A and Y is the number of occurrence of num in B, then add minimum(X, Y) to ans.
  4. Return ans.

Understand With an Example

Let’s say we have

A[]={2, 3, 2, 2, 0, 4}

B[]= {4, 4, 2, 20}

Now we make the hash table for the above arrays.

Remove minimum number of elements such that no common element exist in both array

For element 0, we will add a minimum(1, 0)=0 to the ans.

For element 2, we will add a minimum(3, 1)=1 to the ans.

Now, For element 3, we will add a minimum(1, 0)=0 to the ans.

For element 4, we will add a minimum(1, 2)=1 to the ans.

For element 20, we will add a minimum(0, 1)=0 to the ans.

Final ans=2.

C++ Program for Remove minimum number of elements

#include <bits/stdc++.h>
using namespace std;
int MinElementsToRemove(vector<int> &A, vector<int> &B)
{
    unordered_map<int, int> count_A, count_B;
    for (auto ele : A)
    {
        count_A[ele]++;
    }
    for (auto ele : B)
    {
        count_B[ele]++;
    }
    int ans = 0;
    for (auto ele : count_A)
    {
        if (count_B.count(ele.first) == 1)
        {
            ans += min(count_B[ele.first], count_A[ele.first]);
        }
    }
    return ans;
}
int main()
{
    vector<int> A = {2, 3, 2, 2, 0, 4};
    vector<int> B = {4, 4, 2, 20};
    cout << "Minimum number of elements to remove from each array such that no common element exist in both array: " << MinElementsToRemove(A, B) << endl;
    return 0;
}
Minimum number of elements to remove from each array such that no common element exist between both array: 2

JAVA Program for Remove minimum number of elements

import java.util.*;
public class Main
{
    public static int MinElementsToRemove(int[] A, int[] B)
    {
        Map<Integer, Integer> count_A 
            = new HashMap<Integer, Integer>(); 
        Map<Integer, Integer> count_B
            = new HashMap<Integer, Integer>(); 
        for (int i=0; i<A.length;i++)
        {
            Integer j =count_A.get(A[i]); 
            count_A.put(A[i], (j == null) ? 1 : j + 1); 
        }
        for (int i=0; i<B.length;i++)
        {
            Integer j =count_B.get(B[i]); 
            count_B.put(B[i], (j == null) ? 1 : j + 1); 
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : count_A.entrySet()){
            if (count_B.get(entry.getKey())!=null)
            {
                ans += Math.min(count_B.get(entry.getKey()), count_A.get(entry.getKey()));
            }
        }
        return ans;
    }
  public static void main(String[] args) {
      int[] A = {2, 3, 2, 2, 0, 4};
        int[] B = {4, 4, 2, 20};
    System.out.println("Minimum number of elements to remove from each array such that no common element exist in both array: "+MinElementsToRemove(A, B));
  }
}


Minimum number of elements to remove from each array such that no common element exist between both array: 2

Complexity Analysis for Remove minimum number of elements

Time complexity

As we iterate over both the arrays once, so the total time complexity is O(N+M).

Space complexity

We used two hash tables to store the frequency of elements for both the arrays, so the space complexity is O(N+M).

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions