Minimize insertions or deletions to make the frequency of each array element equal to its value

Approach

We can solve the problem using a greedy approach. You can easily observe that we can deal with the problem separately for each unique element in the array.

Let's say that element ‘X’ is present in the array. Let the frequency of this element be ‘Y’. Now, if Y > X, we are bound to delete excess occurrences of this element. Otherwise, if Y <= X, we are left with two choices:

1. Either insert X - Y to the array.
2. Delete Y occurrences of the elements.

It is not hard to see that we should take the minimum of these two values to minimise the overall number of operations. We can store the frequency of unique elements in the array using a hash map.

Algorithm

1. Take the input array size ‘N’ and the array ‘ARR’ elements.
2. Create an unordered map (or HashMap in Java) to store the frequency of each unique array element.
3. Create a variable ‘MIN_OPERATIONS’ to store the answer.
4. Traverse the unordered map and let the current element be ‘ELEM’ and ‘FREQ’ be its frequency.
   1. If ELEM < FREQ, MIN_OPERATIONS += FREQ - ELEM.
   2. Otherwise, MIN_OPERATIONS += min(ELEM - FREQ, FREQ). These conditions are explained in the approach.
5. Return MIN_OPERATIONS.

Program

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int getMinOperations(int N, vector<int>& arr){
    // Store the frequency of all elements.
    unordered_map<int,int> frequency;
    for(int i = 0; i < N; i++){
        frequency[arr[i]]++;
    }

    // Get the minimum number of operations.
    int minOperations = 0;
    for(auto uniqueElem : frequency){
        // Get the current element and its frequency.
        int elem = uniqueElem.first;
        int freq = uniqueElem.second;

        // First case described in the approach.
        if(freq > elem){
            minOperations += (freq - elem);
        }

        // Second case described in the approach.
        else{
            minOperations += min(elem - freq, freq);
        }
    }

    // Return the output.
    return minOperations;
}

int main(){
    // Enter the size of the array.
    int N;
    cout << "Size of the array: "; 
    cin >> N;

    // Enter the elements.
    vector<int> arr(N);
    cout << "Enter the elements: ";
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }

    // Get the output.
    int ans = getMinOperations(N, arr);
    cout << ans << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Size of the array: 5
Enter the elements: 2 1 3 1 2

Output

2

Time Complexity

The time complexity of the above approach is O(N), where ‘N’ is the size of the array.

It is because, for each element, we are taking a constant amount of time to determine its frequency in the final array.

Space Complexity

The space complexity of the above approach is O(N), where ‘N’ is the size of the array as the size of the unordered_map can grow to N.

Key Takeaways

In this blog, we discussed a simple yet tricky question involving greedy algorithms. Greedy algorithms are one of the well-known topics asked in programming contests and technical interviews. Greedy algorithms are more or less used to test the common sense of the interviewee. Greedy algorithms should be used in problems where we find monotonicity in the result based on specific input factors.

Check out this problem - Search In Rotated Sorted Array