K Most Frequent Words

Problem Link - K Most Frequent Elements

You have been given an array/list 'WORDS' of 'N' non-empty words, and an integer 'K'. Your task is to return the 'K' most frequent words sorted by their frequency from highest to lowest.

Note:

If two words have the same frequency then the lexicographically smallest word should come first in your answer.
Follow up:

Can you solve it in O(N * logK) time and O(N) extra space?

Sample Input 1:
6 2
i love codingninjas i love coding
Sample Output 1:
i love
Sample Input 2:
8 3
the sky is blue the weather is hot
Sample Output 2:
is the blue

Approach

• Declare a map that stores the pair of word and its frequency.
• Iterate through the input list of words and update the frequency of each word in the map. If a word appears for the first time, its frequency is initialized to 1; if it already exists, increment its count.
• Declare a Max-Heap Using a Priority Queue to store word-frequency pairs. By customizing the comparator, you can ensure that words with higher frequencies come out first. In case of a tie (same frequency), you will return the lexicographically smaller word.
• Iterate over the frequency map and insert each word-frequency pair into the priority queue.
• next extract the top k to get the k most frequent elements

Code

#include <bits/stdc++.h>
using namespace std;
class comp{
    public:
        bool operator()(pair<string,int> a,pair<string,int> b){
            if(a.second==b.second){
                return a.first>b.first; // return lexicographically smallest first
            }
            return a.second<b.second;  // return highest frequency first

        }

};

vector<string> kMostFreqWords(string words[], int n, int k){
    // store the frequency of each word in a map
    unordered_map<string,int> mp;
    for(int i=0;i<n;i++){
        mp[words[i]]++;
    }
    // maintaina max-heap using custom comparator
    std::priority_queue<pair<string, int>, vector<pair<string, int>>, comp> pq;
    for(auto it:mp){
        pq.push({it.first,it.second});

    }
    vector<string> ans;
    // extract the top k elements
    while(k-- && !pq.empty()){
        auto it=pq.top();
        pq.pop();
        ans.push_back(it.first);
    }
    return ans;
} 

**
Time Complexity** - O(n)+O(nlogn)+O(klogn)

Approach - 2

Count the frequency of each element using a hash map.
Use a min-heap (priority queue) to store the top k frequencies. If the size of the heap exceeds k, remove the smallest frequency.
Once the heap is built, for each frequency in the heap, find the corresponding element from the frequency map and add it to the result.

Time complexity:

Counting frequencies takes O(n).
Maintaining a heap of size k for each of the n unique elements takes O(n log k).
Overall, the time complexity is O(n log k).