K Most Frequent Words Problem Statement

Given an array or list WORDS of 'N' non-empty words and an integer 'K', identify the 'K' most frequent words and return them sorted by their frequency, in descending order.

Note:

If two words share the same frequency, return them in lexicographical order.

Additionally, consider optimizing your solution to achieve O(N * logK) time complexity with O(N) additional space.

Input:

N K
word1 word2 word3 ... wordN

Output:

wordA wordB ... wordK

Example:

Input:

N = 6, K = 2
WORDS = ['i', 'love', 'leetcode', 'i', 'love', 'coding']

Output:

['i', 'love']

Explanation:

The word 'i' appears twice, as does 'love'. The other words appear only once. Hence, 'i' and 'love' are the most frequent.

Constraints:

1

Question

K Most Frequent Words Problem Statement

Given an array or list WORDS of 'N' non-empty words and an integer 'K', identify the 'K' most frequent words and return them sorted by their frequency, in descending order.

Note:

If two words share the same frequency, return them in lexicographical order.

Additionally, consider optimizing your solution to achieve O(N * logK) time complexity with O(N) additional space.

Input:

N K
word1 word2 word3 ... wordN

Output:

wordA wordB ... wordK

Example:

Input:

N = 6, K = 2
WORDS = ['i', 'love', 'leetcode', 'i', 'love', 'coding']

Output:

['i', 'love']

Explanation:

The word 'i' appears twice, as does 'love'. The other words appear only once. Hence, 'i' and 'love' are the most frequent.

Constraints:

1 <= N <= 10^5
1 <= K <= number of unique words

Time Limit: 1 sec

Accepted Answer

Identify the K most frequent words in a list, sorted by frequency and lexicographical order.

Use a hashmap to store word frequencies
Use a min heap to keep track of K most frequent words
Sort the heap based on frequency and lexicographical order

Asked in Amazon