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.

K_Most_Frequent



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, arg_num, arg_freq) :
        self.num = arg_num
        self.freq = arg_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)

    # 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
[40]

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


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.