Given an array of integers, remove all the elements which appear strictly less than k times.
Examples:
Input : arr[] = {1, 2, 2, 3, 2, 3, 4}
k = 2
Output : 2 2 3 2 3
Explanation : {1, 4} appears less than 2 times.
Approach :
- Take a hash map, which will store the frequency of all the elements in the array.
- Now, traverse once again.
- Remove the elements which appear strictly less than k times.
- Else, print it.
Implementation:
C++
// C++ program to remove the elements which// appear strictly less than k times from the array.#include "iostream"#include "unordered_map"using namespace std;void removeElements(int arr[], int n, int k){ // Hash map which will store the // frequency of the elements of the array. unordered_map<int, int> mp; for (int i = 0; i < n; ++i) { // Incrementing the frequency // of the element by 1. mp[arr[i]]++; } for (int i = 0; i < n; ++i) { // Print the element which appear // more than or equal to k times. if (mp[arr[i]] >= k) { cout << arr[i] << " "; } }}int main(){ int arr[] = { 1, 2, 2, 3, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; removeElements(arr, n, k); return 0;} |
Java
// Java program to remove the elements which // appear strictly less than k times from the array. import java.util.HashMap;class neveropen { public static void removeElements(int[] arr, int n, int k) { // Hash map which will store the // frequency of the elements of the array. HashMap<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < n; ++i) { // Incrementing the frequency // of the element by 1. if (!mp.containsKey(arr[i])) mp.put(arr[i], 1); else { int x = mp.get(arr[i]); mp.put(arr[i], ++x); } } for (int i = 0; i < n; ++i) { // Print the element which appear // more than or equal to k times. if (mp.get(arr[i]) >= k) System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 2, 3, 2, 3, 4 }; int n = arr.length; int k = 2; removeElements(arr, n, k); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 program to remove the elements which# appear strictly less than k times from the array.def removeElements(arr, n, k): # Hash map which will store the # frequency of the elements of the array. mp = dict() for i in range(n): # Incrementing the frequency # of the element by 1. mp[arr[i]] = mp.get(arr[i], 0) + 1 for i in range(n): # Print the element which appear # more than or equal to k times. if (arr[i] in mp and mp[arr[i]] >= k): print(arr[i], end = " ")# Driver Codearr = [1, 2, 2, 3, 2, 3, 4]n = len(arr)k = 2removeElements(arr, n, k)# This code is contributed by Mohit Kumar |
C#
// C# program to remove the elements which // appear strictly less than k times from the array. using System;using System.Collections.Generic; class neveropen { public static void removeElements(int[] arr, int n, int k) { // Hash map which will store the // frequency of the elements of the array. Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < n; ++i) { // Incrementing the frequency // of the element by 1. if (!mp.ContainsKey(arr[i])) mp.Add(arr[i], 1); else { int x = mp[arr[i]]; mp[arr[i]] = mp[arr[i]] + ++x; } } for (int i = 0; i < n; ++i) { // Print the element which appear // more than or equal to k times. if (mp[arr[i]] >= k) Console.Write(arr[i] + " "); } } // Driver code public static void Main(String[] args) { int[] arr = { 1, 2, 2, 3, 2, 3, 4 }; int n = arr.Length; int k = 2; removeElements(arr, n, k); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to remove the elements which// appear strictly less than k times from the array.function removeElements(arr,n,k){ // Hash map which will store the // frequency of the elements of the array. let mp = new Map(); for (let i = 0; i < n; ++i) { // Incrementing the frequency // of the element by 1. if (!mp.has(arr[i])) mp.set(arr[i], 1); else { let x = mp.get(arr[i]); mp.set(arr[i], ++x); } } for (let i = 0; i < n; ++i) { // Print the element which appear // more than or equal to k times. if (mp.get(arr[i]) >= k) document.write(arr[i] + " "); }}// Driver codelet arr=[ 1, 2, 2, 3, 2, 3, 4 ];let n = arr.length;let k = 2;removeElements(arr, n, k);// This code is contributed by unknown2108</script> |
Output
2 2 3 2 3
Time Complexity: O(N)
Auxiliary Space: O(n)
Method #2:Using Built-in Python functions:
- Count the frequencies of every element using Counter() function
- Traverse the array.
- Remove the elements which appear strictly less than k times.
- Else, print it.
Implementation:
C++
// C++ program to remove elements which appear more than k// times in an array#include <iostream>#include <unordered_map>using namespace std;void removeElements(int arr[], int n, int k){ // Creating an unordered_map to store the frequencies unordered_map<int, int> freq; for (int i = 0; i < n; i++) { if (freq.count(arr[i])) { freq[arr[i]]++; } else { freq[arr[i]] = 1; } } // Printing the elements which appear more than or equal // to k times for (int i = 0; i < n; i++) { if (freq[arr[i]] >= k) { cout << arr[i] << " "; } }}int main(){ int arr[] = { 1, 2, 2, 3, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; removeElements(arr, n, k); return 0;} |
Java
import java.util.*;public class Main { public static void removeElements(int[] arr, int n, int k) { // Creating a HashMap to store the frequencies HashMap<Integer, Integer> freq = new HashMap<>(); for (int i = 0; i < n; i++) { if (freq.containsKey(arr[i])) { freq.put(arr[i], freq.get(arr[i]) + 1); } else { freq.put(arr[i], 1); } } // Printing the elements which appear more than or equal to k times for (int i = 0; i < n; i++) { if (freq.get(arr[i]) >= k) { System.out.print(arr[i] + " "); } } } public static void main(String[] args) { int[] arr = {1, 2, 2, 3, 2, 3, 4}; int n = arr.length; int k = 2; removeElements(arr, n, k); }} |
Python3
# Python3 program to remove the elements which# appear strictly less than k times from the array.from collections import Counterdef removeElements(arr, n, k): # Calculating frequencies using # Counter function freq = Counter(arr) for i in range(n): # Print the element which appear # more than or equal to k times. if (freq[arr[i]] >= k): print(arr[i], end=" ")# Driver Codearr = [1, 2, 2, 3, 2, 3, 4]n = len(arr)k = 2removeElements(arr, n, k)# This code is contributed by vikkycirus |
C#
// C# Equivalentusing System;using System.Collections.Generic;public class Program{ public static void removeElements(int[] arr, int n, int k) { // Creating a Dictionary to store the frequencies Dictionary<int, int> freq = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; } else { freq.Add(arr[i], 1); } } // Printing the elements which appear more than or equal to k times for (int i = 0; i < n; i++) { if (freq[arr[i]] >= k) { Console.Write(arr[i] + " "); } } } public static void Main(string[] args) { int[] arr = { 1, 2, 2, 3, 2, 3, 4 }; int n = arr.Length; int k = 2; removeElements(arr, n, k); }} |
Javascript
// JavaScript program to remove the elements which// appear strictly less than k times from the array.let x="";function removeElements(arr, n, k) { // Calculating frequencies using // the reduce() function const freq = arr.reduce((count, val) => { count[val] = (count[val] || 0) + 1; return count; }, {}); for (let i = 0; i < n; i++) { // Print the element which appears // more than or equal to k times. if (freq[arr[i]] >= k) { x = x+ arr[i] + " "; } } console.log(x);}// Driver Codeconst arr = [1, 2, 2, 3, 2, 3, 4];const n = arr.length;const k = 2;removeElements(arr, n, k); |
Output
2 2 3 2 3
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #3:( Space optimization): First we will sort the array and then check if the frequency of array element is greater than or equal to k with the use of binary search function ( Upper_bound ) . Frequency of array element is ‘last_index-first_index+1’ . If the frequency is greater than one , then print it .
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to remove element that occurs// lees than k times in the arrayvoid removeElements(int arr[], int n, int k){ sort(arr, arr + n); // sort array for binary search for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] int first_index = lower_bound(arr, arr + n, arr[i]) - arr; int last_index = upper_bound(arr, arr + n, arr[i]) - arr - 1; int fre = last_index - first_index + 1; // finding frequency if (fre >= k) { // printing element if it is greater // than 1 cout << arr[i] << " "; } }}// Drive codeint main(){ int arr[] = { 1, 2, 2, 3, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; // Function call removeElements(arr, n, k); return 0;}// This Code is contributed by nikhilsainiofficial546 |
Javascript
// javascript implementation of the above approachfunction lower_bound(a, x){ let l = 0; let h = arr.length - 1; while(l <= h){ let m = Math.floor((l + h)/2); if(a[m] < x){ l = m + 1; } else if(a[m] >= x){ h = m - 1; } } return l;}function upper_bound(a, x){ let l = 0; let h = arr.length - 1; while(l <= h){ let m = Math.floor((l + h)/2); if(a[m] <= x){ l = m + 1; } else if(a[m] > x){ h = m - 1; } } return l;}//Function to remove element that occurs // lees than k times in the arrayfunction removeElements(arr, n, k){ arr.sort(); for(let i = 0 ; i < n ;i++) { //index of first and last occ of arr[i] let first_index = lower_bound(arr, arr[i]); let last_index = upper_bound(arr, arr[i])- 1; let fre = last_index-first_index+1;//finding frequency if(fre >= k) { // printing element if it is greater than 1\ process.stdout.write(arr[i] + " "); } } }// Drive codelet arr = [1, 2, 2, 3, 2, 3, 4];let n = arr.length;let k = 2;// Function callremoveElements(arr, n, k); // The code is contributed by Nidhi goel. |
Python3
# Function to remove element that occurs# less than k times in the arraydef removeElements(arr, n, k): arr.sort() # sort array for binary search for i in range(n): # index of first and last occ of arr[i] first_index = bisect.bisect_left(arr, arr[i]) last_index = bisect.bisect_right(arr, arr[i]) - 1 fre = last_index - first_index + 1 # finding frequency if fre >= k: # printing element if it is greater than 1 print(arr[i], end=" ")# Driver codeif __name__ == "__main__": import bisect arr = [1, 2, 2, 3, 2, 3, 4] n = len(arr) k = 2 # Function call removeElements(arr, n, k) |
Java
import java.util.*;class Main { // Function to remove element that occurs // lees than k times in the array static void removeElements(int arr[], int n, int k) { Arrays.sort(arr); // sort array for binary search ArrayList<Integer> arr1 = new ArrayList<Integer>(5); // using add() to initialize values for (int i = 0; i < n; i++) { arr1.add(arr[i]); } for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] int first_index = arr1.indexOf(arr[i]); int last_index = arr1.lastIndexOf(arr[i]); while (last_index < n && arr[last_index] == arr[i]) last_index++; last_index--; int fre = last_index - first_index + 1; // finding frequency if (fre >= k) { // printing element if it is // greater than 1 System.out.print(arr[i] + " "); } } } // Drive code public static void main(String[] args) { int arr[] = { 1, 2, 2, 3, 2, 3, 4 }; int n = arr.length; int k = 2; // Function call removeElements(arr, n, k); }}// This code is contributed by Pratik Gagare (pratikg03) |
C#
using System;using System.Collections.Generic;using System.Linq;class MainClass { // Function to remove element that occurs // less than k times in the array static void RemoveElements(int[] arr, int n, int k) { Array.Sort(arr); // sort array for binary search List<int> arr1 = new List<int>(5); // using Add() to initialize values for (int i = 0; i < n; i++) { arr1.Add(arr[i]); } for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] int first_index = arr1.IndexOf(arr[i]); int last_index = arr1.LastIndexOf(arr[i]); while (last_index < n && arr[last_index] == arr[i]) last_index++; last_index--; int fre = last_index - first_index + 1; // finding frequency if (fre >= k) { // printing element if it is greater than 1 Console.Write(arr[i] + " "); } } } // Drive code public static void Main (string[] args) { int[] arr = { 1, 2, 2, 3, 2, 3, 4 }; int n = arr.Length; int k = 2; // Function call RemoveElements(arr, n, k); }} |
Output
2 2 2 3 3
Time Complexity: O(n*log2n)
Auxiliary Space: O(1)
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!
