K Most Frequent Words

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

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”.