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

Aman Chourasiya
Last Updated: May 13, 2022

Understanding

This blog discusses a coding challenge based on greedy algorithms. Greedy algorithms are based on critical observations and identification of certain factors which increase/decrease monotonically with input size. Sometimes, it is hard to prove the correctness of greedy algorithms as greedy algorithms are intuitive in nature.

Problem Statement

Ninja has given you an array ‘ARR’ of size ‘N’. Your task is to find the minimum number of insertion or deletion operations required to equate the frequency of each array element to its value.

Input

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

Output

2

Explanation

We can delete elements at the second and third indices to make the array satisfy the condition.

Final array: 2 1 2

Input

Size of the array: 8
Enter the elements: 3 3 1 2 2 4 4 4

Output

2

Explanation

We can insert 3 and 4 to the array to make the array satisfy the condition.

Final array: 3 3 1 2 2 4 4 4 3 4

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

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.

 

Was this article helpful ?
0 upvotes