Find k most frequent in linear time

Last Updated: 29-06-2020

Given an array of integers, we need to print k most frequent elements. If there is a tie, we need to prefer the elements whose first appearance is first.

Examples:

Input : arr[] = {10, 5, 20, 5, 10, 10, 30}, k = 2
Output : 10 5

Input : arr[] = {7, 7, 6, 6, 6, 7, 5, 4, 4, 10, 5}, k = 3
Output : 7 6 5
Explanation :
In this example, 7 and 6 have same frequencies. We print 7 first because first appearance of 7 is first. Similarly, 5 and 4 have same frequencies. We prefer 5 because 5’s first appearance is first.

Let us first talk about a simple solution that prints in any order in case of tie. Then we will discuss the solution that takes of the order.

The idea is to use hashing with frequency indexing. We first store counts in a hash. Then we traverse through the hash and use frequencies as index to store elements with given frequencies. The important factor here is, maximum frequency can be n. So an array of size n+1 would be good.

// C++ implementation to find k numbers with most // occurrences in the given array #include <bits/stdc++.h> using namespace std;    // funnction to print the k numbers with most occurrences void print_N_mostFrequentNumber(int arr[], int n, int k) {     // unordered_map 'um' implemented as frequency     // hash table     unordered_map<int, int> um;     for (int i = 0; i < n; i++)         um[arr[i]]++;        // Use frequencies as indexes and put     // elements with given frequency in a     // vector (related to a frequency)     vector<int> freq[n + 1];     for (auto x : um)         freq[x.second].push_back(x.first);        // Initialize count of items printed     int count = 0;        // Traverse the frequency array from     // right side as we need the most     // frequent items.     for (int i = n; i >= 0; i--) {            // Print items of current frequency         for (int x : freq[i]) {             cout << x << " ";             count++;             if (count == k)                 return;         }     } }    // Driver program to test above int main() {     int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };     int n = sizeof(arr) / sizeof(arr[0]);     int k = 2;     print_N_mostFrequentNumber(arr, n, k);     return 0; }

Output:

4 1

Time Complexity : O(n)
Auxiliary Space : O(n)

Printing according to first appearance. To keep the required order, we traverse the original array instead of map. To avoid duplicates, we need to mark processed entries as -1 in map.

// C++ implementation to find k numbers with most // occurrences in the given array #include <bits/stdc++.h> using namespace std;    // function to print the k numbers with most occurrences void print_N_mostFrequentNumber(int arr[], int n, int k) {     // unordered_map 'um' implemented as frequency     // hash table     unordered_map<int, int> um;     for (int i = 0; i < n; i++)         um[arr[i]]++;        // Use frequencies as indexes and put     // elements with given frequency in a     // vector (related to a frequency)     vector<int> freq[n + 1];     for (int i = 0; i < n; i++) {         int f = um[arr[i]];         if (f != -1) {             freq[f].push_back(arr[i]);             um[arr[i]] = -1;         }     }        // Initialize count of items printed     int count = 0;        // Traverse the frequency array from     // right side as we need the most     // frequent items.     for (int i = n; i >= 0; i--) {            // Print items of current frequency         for (int x : freq[i]) {             cout << x << " ";             count++;             if (count == k)                 return;         }     } }    // Driver program to test above int main() {     int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };     int n = sizeof(arr) / sizeof(arr[0]);     int k = 3;     print_N_mostFrequentNumber(arr, n, k);     return 0; }

Output:

1 4 3

Time Complexity : O(n)
Auxiliary Space : O(n)