Home » Technical Interview Questions » Hashing Interview Questions » Minimum Delete Operations to make all Elements of Array Same

Minimum Delete Operations to make all Elements of Array Same


Suppose we have an input of array with “x” number of elements. We have given a problem that we have to find the deletions operations, which should be the minimum that is required to make an equal array i.e., the array will consist of equal elements.

Example

Input:

[1, 1, 4, 6, 2, 1]

Output:

3

Explanation:

After removing (4, 6, 2) 3 elements, the array becomes equal i.e, [1, 1, 1]

Input:

[1, 5, 4, 16, 32, 9]

Output:

5

Explanation:

We can remove any of the 5 elements to make it an equal array.

Algorithm

  1. Store the frequencies of all the elements of the array in a map.
  2. Set “max_freq” to INT_MIN.
  3. Iterate over the map and check what element has a maximum frequency.
    • Set “max_freq” to max(max_freq, value) to find the maximum value among all the frequencies.
  4. Return the difference between array size “n” and max_freq ( n – max_freq ).

Explanation

We have given a problem in which we have to find out how many minimum deletion operations are required to make an array equal (of similar elements). For this, we are going to use a map to store the frequencies of each number that is present in the array.

By doing this, we will have that frequency which is the largest among all the frequencies. By iterating over the map, we can get that maximum frequency by using the max method. After iterating the map we will have the maximum frequency and we need to return array_size  –  maximum frequency, it means we are returning the total number of lesser frequencies that can be removed to make the array equal.

READ  Elements to be added so that all elements of a range are present in array

Let us consider an example:

arr: { 10, 3, 4, 4, 2, 4 };

  • i =  0,  it takes arr [ i ] as 10 and store freq(10, 1).
  • i =  1,  it takes arr [ i ] as 3 and store freq(3, 1).
  • for i =  2,  it takes arr [ i ] as 4 and store freq(4, 1).
  • i =  3,  it takes arr [ i ] as 4, since 4 has already a place in a map it just adds one more count at the key place of 4 and store freq(4, 2).
  • i =  4,  it take arr [ i ] as 2 and store freq(2, 1).
  • for i =  5,  it takes arr [ i ] as 4, since 4 has already a place in a map it just adds one more count at the key place of 4 and store freq(4, 3).

Among all this only number ‘4’ has a maximum frequency which is 3 and after traversing and finding the maximum frequency as 3 from the map, we are going to return the value (n – max_freq) 3. That’s our output.

Implementation

C++ program for Minimum Delete Operations to make all Elements of Array Same

#include <bits/stdc++.h>
using namespace std;

int minDelete(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

Java program for Minimum Delete Operations to make all Elements of Array Same

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

        return n - max_freq;
    }
    public static void main(String args[])
    {
        int arr[] = { 10, 3, 4, 4, 2, 4 };
        int n = arr.length;
        System.out.println(noOfMinimumDeletions(arr, n));
    }
}
3

Complexity Analysis for Minimum Delete Operations to make all Elements of Array Same

Time Complexity

O(n) where “n” is the number of elements in the array

READ  Count quadruples from four sorted arrays whose sum is equal to a given value x

Space Complexity

O(n) where “n” is the number of elements in the array

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

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup