Remove an occurrence of most frequent array element exactly K times

0 0 10 minutes read

Given an array arr[], the task is to remove an occurrence of the most frequent array element exactly K times. If multiple array elements have maximum frequency, remove the smallest of them. Print the K deleted elements.

Examples:

Input: arr[] = {1, 3, 2, 1, 4, 1}, K = 2
Output: 1 1
Explanation:
The frequency of 1 is 3 and frequencies of 2, 3, 4 are 1:
Operation 1: Remove 1 from the array. Currently, the frequency of 1 is 2 and frequencies of 2, 3, 4 is 1.
Operation 2: Remove 1 from the array.

Input: arr[] = {10, 10, 10, 20, 30, 20, 20}, K = 2
Output: 10 20

Naive Approach: The simplest approach is to sort the array in ascending order and count the frequencies of array elements using a Map. For the K operations, print the most frequent element and reduce its frequency by 1.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the most frequent
// array element exactly K times
void maxFreqElements(int arr[],
                     int N, int K)
{
    // Stores frequency array element
    map<int, int> mp;
 
    for (int i = 0; i < N; i++) {
 
        // Count frequency
        // of array element
        mp[arr[i]]++;
    }
 
    while (K > 0) {
 
        // Maximum array element
        int max = 0;
        int element;
 
        // Traverse the Map
        for (auto i : mp) {
 
            // Find the element with
            // maximum frequency
            if (i.second > max) {
                max = i.second;
 
                // If the frequency is maximum,
                // store that number in element
                element = i.first;
            }
        }
 
        // Print element as it contains the
        // element having highest frequency
        cout << element << " ";
 
        // Decrease the frequency
        // of the maximum array element
        mp[element]--;
 
        // Reduce the number of operations
        K--;
    }
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 1, 3, 2, 1, 4, 1 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given K
    int K = 2;
 
    maxFreqElements(arr, N, K);
 
    return 0;
}

Java

// Java program to implement 
// the above approach 
import java.util.*;
class GFG
{
 
// Function to print the most frequent
// array element exactly K times
static void maxFreqElements(int arr[],
                     int N, int K)
{
   
    // Stores frequency array element
    HashMap<Integer,
          Integer> mp = new HashMap<Integer,
                                    Integer>();
  
    for (int i = 0; i < N; i++) 
    {
  
        // Count frequency
        // of array element
        if(mp.containsKey(arr[i]))
            {
                mp.put(arr[i], mp.get(arr[i]) + 1);
            }
            else
            {
                mp.put(arr[i], 1);
            }
    }
  
    while (K > 0) 
    {
  
        // Maximum array element
        int max = 0;
        int element = 0;
  
        // Traverse the Map
        for (Map.Entry<Integer,
                 Integer> i : mp.entrySet()) 
        {
  
            // Find the element with
            // maximum frequency
            if (i.getValue() > max)
            {
                max = i.getValue();
  
                // If the frequency is maximum,
                // store that number in element
                element = i.getKey();
            }
        }
  
        // Print element as it contains the
        // element having highest frequency
        System.out.print(element + " ");
 
  
        // Decrease the frequency
        // of the maximum array element
        if(mp.containsKey(element))
            {
                mp.put(element, mp.get(element) + 1);
            }
            else
            {
                mp.put(element, 1);
            }
 
        // Reduce the number of operations
        K--;
    }
}
  
// Driver code
public static void main(String[] args)
{
    // Given array
    int[] arr = { 1, 3, 2, 1, 4, 1 };
      
    // Size of the array
    int N = arr.length;
      
    // Given K
    int K = 2;   
    maxFreqElements(arr, N, K);
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach 
 
# Function to print the most frequent 
# array element exactly K times 
def maxFreqElements(arr, N, K) : 
 
    # Stores frequency array element 
    mp = {} 
 
    for i in range(N) :
 
        # Count frequency 
        # of array element 
        if arr[i] in mp :
            mp[arr[i]] += 1
        else :
            mp[arr[i]] = 1
 
    while (K > 0) : 
 
        # Maximum array element 
        Max = 0
 
        # Traverse the Map 
        for i in mp :
 
            # Find the element with 
            # maximum frequency 
            if (mp[i] > Max) : 
                Max = mp[i] 
 
                # If the frequency is maximum, 
                # store that number in element 
                element = i
 
        # Print element as it contains the 
        # element having highest frequency 
        print(element, end = " ") 
 
        # Decrease the frequency 
        # of the maximum array element 
        if element in mp :
            mp[element] -= 1
        else :
            mp[element] = -1
 
        # Reduce the number of operations 
        K -= 1
 
# Given array 
arr = [ 1, 3, 2, 1, 4, 1 ] 
 
# Size of the array 
N = len(arr)  
 
# Given K 
K = 2
 
maxFreqElements(arr, N, K)
 
# This code is contributed by divyeshrabadiya07

C#

// C# program for the above approach
using System;
using System.Collections.Generic;  
 
class GFG{
     
// Function to print the most frequent
// array element exactly K times
static void maxFreqElements(int[] arr, 
                            int N, int K)
{
     
    // Stores frequency array element
    Dictionary<int,
               int> mp = new Dictionary<int, 
                                        int>();  
                                         
    for(int i = 0; i < N; i++)
    {
         
        // Count frequency
        // of array element
        if (mp.ContainsKey(arr[i]))
        {
            mp[arr[i]]++;
        }
        else
        {
            mp[arr[i]] = 1;
        }
    }
  
    while (K > 0)
    {
         
        // Maximum array element
        int max = 0;
        int element = 0;
  
        // Traverse the Map
        foreach(KeyValuePair<int, int> i in mp)
        {
             
            // Find the element with
            // maximum frequency
            if (i.Value > max) 
            {
                max = i.Value;
                 
                // If the frequency is maximum,
                // store that number in element
                element = i.Key;
            }
        }
  
        // Print element as it contains the
        // element having highest frequency
        Console.Write(element + " ");
  
        // Decrease the frequency
        // of the maximum array element
        if (mp.ContainsKey(element))
        {
            mp[element]--;
        }
        else
        {
            mp[element] = -1;
        }
  
        // Reduce the number of operations
        K--;
    }
}
 
// Driver Code
static void Main() 
{
     
    // Given array
    int[] arr = { 1, 3, 2, 1, 4, 1 };
     
    // Size of the array
    int N = arr.Length;
     
    // Given K
    int K = 2;
     
    maxFreqElements(arr, N, K);
}
}
 
// This code is contributed by divyesh072019

Javascript

<script>
 
      // JavaScript program for the above approach
       
      // Function to print the most frequent
      // array element exactly K times
      function maxFreqElements(arr, N, K) {
        // Stores frequency array element
        var mp = {};
 
        for (var i = 0; i < N; i++) {
          // Count frequency
          // of array element
          if (mp.hasOwnProperty(arr[i])) {
            mp[arr[i]]++;
          } else {
            mp[arr[i]] = 1;
          }
        }
 
        while (K > 0) {
          // Maximum array element
          var max = 0;
          var element = 0;
 
          // Traverse the Map
          for (const [key, value] of Object.entries(mp)) {
            // Find the element with
            // maximum frequency
            if (value > max) {
              max = value;
 
              // If the frequency is maximum,
              // store that number in element
              element = key;
            }
          }
 
          // Print element as it contains the
          // element having highest frequency
          document.write(element + " ");
 
          // Decrease the frequency
          // of the maximum array element
          if (mp.hasOwnProperty(element)) {
            mp[element]--;
          } else {
            mp[element] = -1;
          }
 
          // Reduce the number of operations
          K--;
        }
      }
 
      // Driver Code
      // Given array
      var arr = [1, 3, 2, 1, 4, 1];
 
      // Size of the array
      var N = arr.length;
 
      // Given K
      var K = 2;
 
      maxFreqElements(arr, N, K);
</script>

Output:

1 1

Time Complexity: O(N * K)
Auxiliary Space: O(N)

Efficient Approach: The idea is to store the array of elements in a vector of pairs along with their count and then sort the vector of pairs in ascending order using a comparator. Once done, print the first K elements from that vector of pairs.

Follow the steps below to solve the problem:

Initialize a Map to store the frequency of array elements. Initialize a vector of pairs to store {element, frequency}.
Sort the vector of pairs in descending order of the second value.
Then, print the array elements of the first K pairs as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the vector
// of vector of pair
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    // Check if frequency of p1 is
    // greater than frequency of p2
    if (p1.second > p2.second)
        return true;
 
    // If frequency of p1 and p2 is same
    else if (p1.second == p2.second) {
 
        // Check for the smallest element
        if (p1.first < p2.first)
            return true;
    }
    return false;
}
 
// Function to print the K most frequent
// elements after each removal
void maxFreqElements(int arr[], int N, int K)
{
    // Stores frequency of array elements
    map<int, int> mp;
 
    // Pairs array element with frequency
    vector<pair<int, int> > v;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Count the frequencies
        mp[arr[i]]++;
 
        // Insert the element with its
        // current frequency into the vector
        v.push_back({ arr[i], mp[arr[i]] });
    }
 
    // Sort the vector according to
    // higher frequency and smaller
    // element if frequency is same
    sort(v.begin(), v.end(), cmp);
 
    // Print the first K elements
    // of the array
    for (int i = 0; i < K; i++)
        cout << v[i].first << " ";
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 1, 3, 2, 1, 4, 1 };
 
    // Given K
    int K = 2;
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    maxFreqElements(arr, N, K);
 
    return 0;
}

Java

// Java program for above approach
import java.util.*;
import java.lang.*;
 
class pair{
    int first,second;
     
    pair(int first, int second){
        this.first=first;
        this.second=second;
    }
}
class GFG{
  
// Function to print the K most frequent
// elements after each removal
static void maxFreqElements(int arr[], int N, int K)
{
    // Stores frequency of array elements
    Map<Integer, Integer> mp=new HashMap<>();
  
    // Pairs array element with frequency
    ArrayList<pair> v=new ArrayList<>();
  
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
  
        // Count the frequencies
        mp.put(arr[i],mp.getOrDefault(arr[i],0)+1);
  
        // Insert the element with its
        // current frequency into the vector
        v.add(new pair( arr[i], mp.get(arr[i] )));
    }
  
    // Sort the vector according to
    // higher frequency and smaller
    // element if frequency is same
   Collections.sort(v,(a,b)->(a.second != b.second) ? 
                    b.second-a.second:a.first-b.first);
  
    // Print the first K elements
    // of the array
    for (int i = 0; i < K; i++)
        System.out.print(v.get(i).first + " ");
}
   
   // Driver function
    public static void main (String[] args)
    {
      
    // Given array
    int arr[] = { 1, 3, 2, 1, 4, 1 };
  
    // Given K
    int K = 2;
  
    // Size of the array
    int N = arr.length;
  
    maxFreqElements(arr, N, K);
  
    }
}
 
// This code is contributed by offbeat

Python3

# Python 3 program for the above approach
 
# Function to sort the vector
# of vector of pair
 
# Function to print the K most frequent
# elements after each removal
def maxFreqElements(arr, N, K):
   
    # Stores frequency of array elements
    mp = {}
 
    # Pairs array element with frequency
    v = []
 
    # Traverse the array
    for i in range(N):
        # Count the frequencies
        mp[arr[i]] = mp.get(arr[i],0)+1
 
        # Insert the element with its
        # current frequency into the vector
        v.append([arr[i], mp.get(arr[i],0)])
 
    # Sort the vector according to
    # higher frequency and smaller
    c = [1, 1]
     
    # element if frequency is same
    v.sort(reverse = True)
 
    # Print the first K elements
    # of the array   
    for i in range(K):
        print(c[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [1, 3, 2, 1, 4, 1]
 
    # Given K
    K = 2
 
    # Size of the array
    N = len(arr)
 
    maxFreqElements(arr, N, K)
     
    # This code is contributed by SURANDRA_GANGWAR.

C#

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class pair
{
  public int first, second;
 
  public pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
public class GFG{
 
  static int Compare(KeyValuePair<int, int> a, KeyValuePair<int, int> b)
  {
    if(a.Value != b.Value)
    {
      return b.Value - a.Value;
    }
    else
    {
      return a.Key - b.Key;
    }
  }
 
  // Function to print the K most frequent
  // elements after each removal
  static void maxFreqElements(int[] arr, int N, int K)
  {
     
    // Stores frequency of array elements
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Pairs array element with frequency
    List<KeyValuePair<int,int>> v = new List<KeyValuePair<int,int>>();
     
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // Count the frequencies
      if(!mp.ContainsKey(arr[i]))
      {
        mp.Add(arr[i], 1);
      }
      else
      {
        mp[arr[i]]++;
      }
 
      // Insert the element with its
      // current frequency into the vector
      v.Add(new KeyValuePair<int,int>( arr[i], mp[arr[i] ]));
    }
    v.Sort(Compare);
 
    // Print the first K elements
    // of the array
    for (int i = 0; i < K; i++)
    {
      Console.Write(v[i].Key + " ");
    }
  }
 
  // Driver function
  static public void Main ()
  {
 
    // Given array
    int[] arr = { 1, 3, 2, 1, 4, 1 };
 
    // Given K
    int K = 2;
 
    // Size of the array
    int N = arr.Length;
 
    maxFreqElements(arr, N, K);
  }
}
 
// This code is contributed by rag2127.

Javascript

<script>
 
 
// Javascript program for the above approach
 
// Function to print the K most frequent
// elements after each removal
function maxFreqElements(arr, N, K)
{
    // Stores frequency of array elements
    var mp = new Map();
 
    // Pairs array element with frequency
    var v = [];
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Count the frequencies
        if(mp.has(arr[i]))
            mp.set(arr[i], mp.get(arr[i])+1)
        else
            mp.set(arr[i], 1)
 
        // Insert the element with its
        // current frequency into the vector
        v.push([arr[i], mp.get(arr[i])]);
    }
 
    // Sort the vector according to
    // higher frequency and smaller
    // element if frequency is same
    v.sort();
 
    // Print the first K elements
    // of the array
    for (var i = 0; i < K; i++)
        document.write( v[i][0] + " ");
}
 
// Driver Code
// Given array
var arr = [1, 3, 2, 1, 4, 1];
// Given K
var K = 2;
// Size of the array
var N = arr.length
maxFreqElements(arr, N, K);
 
 
</script>

Output:

1 1

Time Complexity: O(NlogN)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!