Last Updated: 2 Sep, 2020
K Most Frequent Words
Moderate
Asked in companies
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?
Input Format:
The first line of input contains two integers, N and K, where N is the number of the words and, K denotes the number of words to return.
The next line contains N single space-separated words. Each word consists of only lowercase Latin letters.
Output Format:
For each input, print K single space-separated words, where the ith word denotes the ith most frequent word.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= N <= 10^5
1 <= K <= number of unique words
Time Limit: 1sec
Approaches
We use a hashmap<key, value> to store the frequencies of all unique words in the list, where the key is the word and value is the frequency of that word in the list. While iterating over each word, we will increment the frequency corresponding to that word in the hashmap by 1.
Now, we need to find the K largest frequencies among them. For this, we store each word and its frequency as a pair in a list. We then sort the list based on the criteria that the word having a higher frequency should come first. In case if two words have the same frequency, we compare the words and the lexicographically smaller word should come first.
After sorting, the first K words of the list would be our required answer.
We use a hashmap<key, value> to store the frequencies of all unique words in the list, where the key is the word and value is the frequency of that word in the list. While iterating over each word, we will increment the frequency corresponding to that word in the hashmap by 1.
Now, we need to find the K largest frequencies among them. For this, we will first initialize a min-heap of size K that will keep the least frequency word as the top(root) element. When two words have the same frequencies we will keep the lexicographically larger word at the top of other words in the min-heap(as the lexicographically larger word will have the least priority from all top most K words).
Now, iterating through the Hashmap, we will add first K words into the min-heap. For the next words, we will compare the frequency of the current word with the minimum frequency from the heap(top element of min heap). If the current frequency is larger than the minimum frequency from the heap. We will pop the top element from the min-heap and insert our current word into the list. Otherwise, if the current frequency is equal to the minimum frequency then we will compare both the words and only keep the lexicographically smaller word from them.
Now, our min heap will be storing the top K most frequent words. We will pop all words in a list. This list will now contain the least frequent word out of these K words at the 0th position and the most frequent word at the (K - 1)th position. This means we need to return the reverse of this list as our answer.