Problem

Submissions

Hints & solutions

Discuss

K Most Frequent Words

Moderate

0/80

Average time to solve is 36m

22 upvotes

Asked in companies

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )

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

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

Explanation for Sample Input 2:

“is” and “the” are words with a frequency of 2.
“sky”, “blue”, “weather”, and “hot” are the words with a frequency of 1.

The words with a frequency of 2 are the most frequent words and the lexicographically smallest word from the words with a frequency of 1 is “blue”.

Hint 1

Hint 2

Use a data structure to store the frequency of all unique strings. The task that remains is to find the k largest frequencies.

Approaches (2)

Approach 1

Approach 2

Using Sorting

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.

Time Complexity

O(N * logN), where N is the number of the words.

Hashing each word would require O(N) time. Sorting the list would require O(N * logN) time.

Space Complexity

O(N), where N is the number of the words.

In the worst case, we will be storing all the N-words in the map, and in the list, both requires O(N) space.

(100% EXP penalty)

K Most Frequent Words

Console