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 timesvoid 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 Codeint 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 timesstatic 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 codepublic 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 = 2maxFreqElements(arr, N, K)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;using System.Collections.Generic; class GFG{ // Function to print the most frequent// array element exactly K timesstatic 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 Codestatic 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 pairbool 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 removalvoid 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 Codeint 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 approachimport 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 removalstatic 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 removaldef 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 Codeif __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 approachusing 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 removalfunction 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 arrayvar arr = [1, 3, 2, 1, 4, 1];// Given Kvar K = 2;// Size of the arrayvar N = arr.lengthmaxFreqElements(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
