# Finding the K most frequent elements in an array

To find the K most frequent elements present in an array we do the following

1. Find the frequency of each element by iterating over the given array. Store the < element, frequency > into a map / dictionary.
2. Create a max-heap using the items in the map / dictionary.
3. To find the K most frequent elements in the array, return the top-most K items from the max-heap. Program for finding the top k most frequent elements in an array.

``````from typing import List # For annotations
import heapq

class MostFreq :

def __init__ (self, num, freq) :
self.num = num
self.freq = freq

# Highest frequency element goes at the top.
# As heapq by default is a min-heap, we override the
# __lt__ (less than) or __gt__ (greater than) function to convert
# the heapq of the objects of MostFreq from a min-heap to a max-heap

#def __gt__ (self, arg_obj) :
#    return self.freq < arg_obj.freq

def __lt__ (self, arg_obj) :
return self.freq > arg_obj.freq

def __eq__ (self, arg_obj) :
return self.freq == arg_obj.freq

def K_TopMost_Frequent (num_list : List[int], k : int) -> List[int] :

list_mostfreq = []
freq = {}
result_mostfreq = []

# Store the frequency of all the numbers in a dictionary.
for num in num_list :
if num not in freq :
freq[num] = 1
else :
freq[num] += 1

# Create a max (frequency) heap from the entries stored in a dictionary
for key, value in freq.items() :
obj = MostFreq(key, value)
heapq.heappush(list_mostfreq, obj) # The list_mostfreq is now a max heap

# Store the top-most k elements from the max heap in the list
count = 0
while (count < k and len(list_mostfreq) > 0 ) :
obj = heapq.heappop(list_mostfreq)
result_mostfreq.append(obj.num)
count += 1

return result_mostfreq

def main() :

num = [ 1, 1, 1, 2, 2, 3, 40, 40, 40, 40, 40, 10, 10, 12, 12, 7, 7, 7, 7 ]
print("Array numbers : " + str(num))

print("Fetching most frequent k elements in the array.")
k = int(input("Enter k : "))

result = K_TopMost_Frequent(num, k)
print(result)

if __name__ == "__main__" :
main()
``````

Output

``````Array numbers : [1, 1, 1, 2, 2, 3, 40, 40, 40, 40, 40, 10, 10, 12, 12, 7, 7, 7, 7]
Fetching most frequent k elements in the array.
Enter k : 5
[40, 7, 1, 12, 10]

Array numbers : [1, 1, 1, 2, 2, 3, 40, 40, 40, 40, 40, 10, 10, 12, 12, 7, 7, 7, 7]
Fetching most frequent k elements in the array.
Enter k : 1


Array numbers : [1, 1, 1, 2, 2, 3, 40, 40, 40, 40, 40, 10, 10, 12, 12, 7, 7, 7, 7]
Fetching most frequent k elements in the array.
Enter k : 2
[40, 7]
``````
``````#include<iostream>
#include<vector>
#include<map>
#include<queue>

class MostFreq {
public:
int num;
int freq;
MostFreq (int arg_num, int arg_freq) : num(arg_num), freq(arg_freq)
{}

// To store the least frequent element at the top, just change the frequency
// comparision.
// Highest frequency element goes at the top.
bool operator < (const MostFreq& obj) const {
if (this->freq <= obj.freq)
return true;
return false;
}
};

std :: vector<int> K_TopMost_Frequent (std :: vector<int>& nums, int k) {

std :: priority_queue<MostFreq> pq_mostfreq;
std :: map<int, int> freq;
std :: vector<int> vec_mostfreq;

// Store the frequency of all the numbers in a map.
for (const auto& n : nums) {
if (freq.find(n) != freq.end())
freq[n]++;
else
freq[n] = 1;
}

// Create a max (frequency) heap from the entries store in a map.
for (const auto m : freq) {
MostFreq obj(m.first, m.second);
pq_mostfreq.push(obj);
}

// Store the top-most k elements from the max heap into the vector
int count = 0;
while (count < k && !pq_mostfreq.empty()) {
MostFreq obj = pq_mostfreq.top();
pq_mostfreq.pop();
vec_mostfreq.push_back(obj.num);
count++;
}

return vec_mostfreq;
}

int main() {

std :: vector<int> num { 1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 10, 10, 10, 10 };
std :: cout << "Array numbers : ";
for (const auto& n : num)
std :: cout << n << " ";

int k;
std :: cout << "\nFetching most frequent k elements in the array." << std :: endl;
std :: cout << "Enter k : ";
std :: cin >> k;

std :: vector<int> result = K_TopMost_Frequent(num, k);
for (const auto& n : result)
std :: cout << n << " ";
return 0;
}
``````

Output

``````Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most frequent k elements in the array.
Enter k : 4
4 10 1 2

Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most frequent k elements in the array.
Enter k : 1
4

Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most / least frequent k elements in the array.
Enter k : 2
4 10

Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most / least frequent k elements in the array.
Enter k : 5
4 10 1 2 3
``````
``````import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.HashMap;

class MostFreq {

int num; // Store the number
int freq; // Store the count of 'number' present in the array

MostFreq () {
}

MostFreq (int arg_num, int arg_freq) {
num = arg_num;
freq = arg_freq;
}

// Highest frequency element goes at the top.
public int[] K_TopMost_Frequent (int[] nums, int k) {

// Max-Heap using PriorityQueue to store the objects based on the frequency
PriorityQueue<MostFreq> pq_mostfreq = new PriorityQueue<>((obj_x, obj_y) -> Integer.compare(obj_y.freq, obj_x.freq));

HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();

int[] result = new int[k];

// Store the frequency of all the numbers in a map.
for (int n : nums) {
if (freq.get(n) != null) {
int count = freq.get(n);
freq.put(n, count+1);
} else {
freq.put(n, 1);
}
}

// Create a max (frequency) heap from the entries stored in the map.
freq.forEach ((key, value) -> pq_mostfreq.add(new MostFreq(key, value)));

// Store the top-most k elements from the max heap into the vector
int count = 0;
while (count < k && !pq_mostfreq.isEmpty()) {
MostFreq obj = pq_mostfreq.remove();
result[count] = obj.num;
count++;
}

return result;
}

public static void main (String[] args) {

int[] nums = { 1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 4, 10, 10, 10, 10 };

System.out.print("Array numbers : ");
for (int n : nums)
System.out.print(n + " ");

System.out.println("\nFetching most frequent k elements in the array.");
System.out.print("Enter k : ");

Scanner sc = new Scanner(System.in);
int k = sc.nextInt();

MostFreq obj = new MostFreq();

int[] result = obj.K_TopMost_Frequent(nums, k);
for (int n : result)
System.out.print(n + " ");
}
}
``````

Output

``````Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most frequent k elements in the array.
Enter k : 2
4 10
Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most frequent k elements in the array.
Enter k : 5
4 10 1 2 3

Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most frequent k elements in the array.
Enter k : 3
4 10 1

Array numbers : 1 1 1 2 2 3 4 4 4 4 4 10 10 10 10
Fetching most frequent k elements in the array.
Enter k : 2
3 2
``````