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.

Table of Contents

Example

Input:

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

Output:

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:

Explanation:

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

Algorithm

Store the frequencies of all the elements of the array in a map.
Set “max_freq” to INT_MIN.
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.
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.

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;
}

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));
    }
}

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

Space Complexity

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