Remove array elements to reduce frequency of each array element to at most K
Given a sorted array arr[] of size N and an integer K, the task is to print the array by removing the minimum number of array elements to make frequency of each element at most K.
Examples:
Input: arr[] = { 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5 }, K = 3
Output: { 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5 }
Explanation:
Removing arr[0], arr[8] modifies arr[] to { 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5 }.
The frequency of each distinct array element is at most K(=3).
Therefore, the required output is { 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5 }.Input: arr[] = { 1, 2, 2, 3, 4, 4, 4, 5, 5 }, K = 2
Output: { 1, 2, 2, 3, 4, 4, 5, 5 }
Naive Approach: The simplest approach to solve this problem is to traverse the array and check if the frequency of the array elements is greater than K or not. If found to be true, then remove the current element from the array. Otherwise, increment the frequency of the array element and print the array element.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below to solve the problem:
- Initialize a variable, say j = 0 to store the index of any array element by removing the array elements such that the frequency of each distinct element is at most K.
- Traverse the array and check if j < K or arr[i] > arr[j – K] is true or not. If found to be true, then update arr[j++] = arr[i].
- Finally, print the array by removing all the array elements whose index is greater than or equal to j.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to remove array elements // such that frequency of each distinct // array element is at most K vector< int > RemoveElemArr(vector< int >& arr, int n, int k) { // Base Case if (n == 0 || n == 1) return arr; // Stores index of array element by removing // the array element such that the frequency // of array elements is at most K int j = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If j < k or arr[i] > arr[j - k] if (j < k || arr[i] > arr[j - k]) { // Update arr[j] arr[j++] = arr[i]; } } // Remove array elements while (arr.size() > j) { arr.pop_back(); } return arr; } // Function to print the array void printArray(vector< int >& arr) { // Traverse the array for ( int i = 0; i < arr.size(); i++) { cout << arr[i] << " " ; } } // Utility Function to remove array elements // such that frequency of each distinct // array element is at most K void UtilRemov(vector< int >& arr, int n, int k) { arr = RemoveElemArr(arr, n, k); // Print updated array printArray(arr); } // Driver Code int main() { vector< int > arr = { 1, 2, 2, 3, 4, 4, 4, 5, 5 }; int k = 2; int n = arr.size(); UtilRemov(arr, n, k); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to remove array elements // such that frequency of each distinct // array element is at most K static int [] RemoveElemArr( int []arr, int n, int k) { // Base Case if (n == 0 || n == 1 ) return arr; // Stores index of array element by removing // the array element such that the frequency // of array elements is at most K int j = 0 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // If j < k or arr[i] > arr[j - k] if (j < k || arr[i] > arr[j - k]) { // Update arr[j] arr[j++] = arr[i]; } } // Remove array elements while (arr.length > j) { arr = Arrays.copyOfRange(arr, 0 , arr.length- 1 ); } return arr; } // Function to print the array static void printArray( int [] arr) { // Traverse the array for ( int i = 0 ; i < arr.length; i++) { System.out.print(arr[i]+ " " ); } } // Utility Function to remove array elements // such that frequency of each distinct // array element is at most K static void UtilRemov( int []arr, int n, int k) { arr = RemoveElemArr(arr, n, k); // Print updated array printArray(arr); } // Driver Code public static void main(String[] args) { int []arr = { 1 , 2 , 2 , 3 , 4 , 4 , 4 , 5 , 5 }; int k = 2 ; int n = arr.length; UtilRemov(arr, n, k); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function to remove array elements # such that frequency of each distinct # array element is at most K def RemoveElemArr(arr, n, k): # Base Case if (n = = 0 or n = = 1 ): return arr # Stores index of array element by # removing the array element such # that the frequency of array # elements is at most K j = 0 # Traverse the array for i in range (n): # If j < k or arr[i] > arr[j - k] if (j < k or arr[i] > arr[j - k]): # Update arr[j] arr[j], j = arr[i], j + 1 # Remove array elements while ( len (arr) > j): del arr[ - 1 ] return arr # Function to print the array def printArray(arr): # Traverse the array for i in arr: print (i, end = " " ) # Utility Function to remove array elements # such that frequency of each distinct # array element is at most K def UtilRemov(arr, n, k): arr = RemoveElemArr(arr, n, k) # Print updated array printArray(arr) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 2 , 3 , 4 , 4 , 4 , 5 , 5 ] k = 2 n = len (arr) UtilRemov(arr, n, k) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; using System.Linq; class GFG { // Function to remove array elements // such that frequency of each distinct // array element is at most K static int [] RemoveElemArr( int []arr, int n, int k) { // Base Case if (n == 0 || n == 1) return arr; // Stores index of array element by removing // the array element such that the frequency // of array elements is at most K int j = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If j < k or arr[i] > arr[j - k] if (j < k || arr[i] > arr[j - k]) { // Update arr[j] arr[j++] = arr[i]; } } // Remove array elements while (arr.Length > j) { arr = arr.Take(arr.Length - 1).ToArray(); } return arr; } // Function to print the array static void printArray( int [] arr) { // Traverse the array for ( int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " " ); } } // Utility Function to remove array elements // such that frequency of each distinct // array element is at most K static void UtilRemov( int []arr, int n, int k) { arr = RemoveElemArr(arr, n, k); // Print updated array printArray(arr); } // Driver code public static void Main() { int []arr = { 1, 2, 2, 3, 4, 4, 4, 5, 5 }; int k = 2; int n = arr.Length; UtilRemov(arr, n, k); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach // Function to remove array elements // such that frequency of each distinct // array element is at most K function RemoveElemArr(arr, n, k) { // Base Case if (n == 0 || n == 1) return arr; // Stores index of array element by removing // the array element such that the frequency // of array elements is at most K var j = 0; // Traverse the array for ( var i = 0; i < n; i++) { // If j < k or arr[i] > arr[j - k] if (j < k || arr[i] > arr[j - k]) { // Update arr[j] arr[j++] = arr[i]; } } // Remove array elements while (arr.length > j) { arr.pop(); } return arr; } // Function to print the array function printArray(arr) { // Traverse the array for ( var i = 0; i < arr.length; i++) { document.write(arr[i] + " " ); } } // Utility Function to remove array elements // such that frequency of each distinct // array element is at most K function UtilRemov(arr, n, k) { arr = RemoveElemArr(arr, n, k); // Print updated array printArray(arr); } var arr = [ 1, 2, 2, 3, 4, 4, 4, 5, 5 ]; var k = 2; var n = arr.length; UtilRemov(arr, n, k); // This code is contributed by SoumikMondal </script> |
1 2 2 3 4 4 5 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Using dictionary to count frequency in python:
Approach:
Create a dictionary to store the frequency of each element in the array.
Iterate over the array and check the frequency of each element. If the frequency of an element is less than or equal to K, add it to a new array and decrement its frequency in the dictionary.
Return the new array.
C++
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // Function to reduce the frequency of elements in the array // such that no element appears more than k times vector< int > reduceFrequency( const vector< int >& arr, int k) { // Create an unordered_map to store the frequency of each element unordered_map< int , int > freq; for ( int i : arr) { // Increase the frequency count of element i if (freq.find(i) != freq.end()) { freq[i]++; } else { // If i is not in the map, initialize its frequency to 1 freq[i] = 1; } } // Create a new vector to store the reduced array vector< int > new_arr; for ( int i : arr) { // If the frequency of element i is less than or equal to k, include it in the new array if (freq[i] <= k) { new_arr.push_back(i); } // Decrease the frequency count of element i by 2 freq[i] -= 2; } return new_arr; } int main() { // Example 1 vector< int > arr1 = {1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5}; int k1 = 3; vector< int > result1 = reduceFrequency(arr1, k1); cout << "Reduced Array 1: " ; for ( int i : result1) { cout << i << " " ; } cout << endl; // Example 2 vector< int > arr2 = {1, 2, 2, 3, 4, 4, 4, 5, 5}; int k2 = 2; vector< int > result2 = reduceFrequency(arr2, k2); cout << "Reduced Array 2: " ; for ( int i : result2) { cout << i << " " ; } cout << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Main { // Function to reduce the frequency of elements in the array // such that no element appears more than k times public static List<Integer> reduceFrequency(List<Integer> arr, int k) { // Create a HashMap to store the frequency of each element Map<Integer, Integer> freq = new HashMap<>(); for ( int i : arr) { // Increase the frequency count of element i freq.put(i, freq.getOrDefault(i, 0 ) + 1 ); } // Create a new ArrayList to store the reduced array List<Integer> new_arr = new ArrayList<>(); for ( int i : arr) { // If the frequency of element i is less than or equal to k, include it in the new array if (freq.get(i) <= k) { new_arr.add(i); } // Decrease the frequency count of element i by 2 freq.put(i, freq.getOrDefault(i, 0 ) - 2 ); } return new_arr; } public static void main(String[] args) { // Example 1 List<Integer> arr1 = List.of( 1 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 4 , 4 , 4 , 4 , 5 ); int k1 = 3 ; List<Integer> result1 = reduceFrequency(arr1, k1); System.out.print( "Reduced Array 1: " ); for ( int i : result1) { System.out.print(i + " " ); } System.out.println(); // Example 2 List<Integer> arr2 = List.of( 1 , 2 , 2 , 3 , 4 , 4 , 4 , 5 , 5 ); int k2 = 2 ; List<Integer> result2 = reduceFrequency(arr2, k2); System.out.print( "Reduced Array 2: " ); for ( int i : result2) { System.out.print(i + " " ); } System.out.println(); } } // This code is contributed by rambabuguphka |
Python3
def reduce_frequency(arr, k): freq = {} for i in arr: if i in freq: freq[i] + = 1 else : freq[i] = 1 new_arr = [] for i in arr: if freq[i] < = k: new_arr.append(i) freq[i] - = 2 return new_arr # Example 1 arr1 = [ 1 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 4 , 4 , 4 , 4 , 5 ] k1 = 3 print (reduce_frequency(arr1, k1)) # Example 2 arr2 = [ 1 , 2 , 2 , 3 , 4 , 4 , 4 , 5 , 5 ] k2 = 2 print (reduce_frequency(arr2, k2)) |
C#
using System; using System.Collections.Generic; class Program { // Function to reduce the frequency of elements in the array // such that no element appears more than k times static List< int > ReduceFrequency(List< int > arr, int k) { // Create a dictionary to store the frequency of each element Dictionary< int , int > freq = new Dictionary< int , int >(); foreach ( int i in arr) { // Increase the frequency count of element i if (freq.ContainsKey(i)) { freq[i]++; } else { // If i is not in the dictionary, initialize its frequency to 1 freq[i] = 1; } } // Create a new list to store the reduced array List< int > new_arr = new List< int >(); foreach ( int i in arr) { // If the frequency of element i is less than or equal to k, include it in the new list if (freq[i] <= k) { new_arr.Add(i); } // Decrease the frequency count of element i by 2 freq[i] -= 2; } return new_arr; } static void Main( string [] args) { // Example 1 List< int > arr1 = new List< int > { 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5 }; int k1 = 3; List< int > result1 = ReduceFrequency(arr1, k1); Console.Write( "Reduced Array 1: " ); foreach ( int i in result1) { Console.Write(i + " " ); } Console.WriteLine(); // Example 2 List< int > arr2 = new List< int > { 1, 2, 2, 3, 4, 4, 4, 5, 5 }; int k2 = 2; List< int > result2 = ReduceFrequency(arr2, k2); Console.Write( "Reduced Array 2: " ); foreach ( int i in result2) { Console.Write(i + " " ); } Console.WriteLine(); } } |
Javascript
// Function to reduce the frequency of elements in the array // such that no element appears more than k times function reduceFrequency(arr, k) { // Create an object to store the frequency of each element const freq = {}; for (let i of arr) { // Increase the frequency count of element i if (freq[i] !== undefined) { freq[i]++; } else { // If i is not in the object, initialize its frequency to 1 freq[i] = 1; } } // Create a new array to store the reduced elements const new_arr = []; for (let i of arr) { // If the frequency of element i is less than or equal to k, include it in the new array if (freq[i] <= k) { new_arr.push(i); } // Decrease the frequency count of element i by 2 freq[i] -= 2; } return new_arr; } // Example 1 const arr1 = [1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5]; const k1 = 3; const result1 = reduceFrequency(arr1, k1); console.log(result1.join( ' ' )); // Example 2 const arr2 = [1, 2, 2, 3, 4, 4, 4, 5, 5]; const k2 = 2; const result2 = reduceFrequency(arr2, k2); console.log(result2.join( ' ' )); |
[1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5] [1, 2, 2, 3, 4, 4, 5, 5]
Time Complexity: O(n)
Space Complexity: O(n)
Contact Us