Solution: Top K Frequent Words
Let’s solve the Top K Frequent Words problem using the Trie pattern.
We'll cover the following
Statement
Given a list of strings words
and an integer k
, return the k
most frequently occurring strings.
Note: The result should be sorted in descending order based on frequency. If multiple words have the same frequency, they should be sorted in lexicographical order.
Constraints:
words.length
words[i].length
k
number of unique words in the list words[i]
consists of lowercase English letters.
Solution
This solution utilizes the trie data structure and bucket sort method to find the top k elements in a list. It achieves this by combining a bucket sort technique (which groups words based on their frequencies), a trie (which stores words in an organized manner), and a frequency map (which counts the occurrences of each word).
Let’s look at the step-by-step implementation of the solution:
Initialize a
frequencyMap
dictionary to count the frequency of each word in thewords
list.Create a list of buckets where the index represents the frequency of words. The length of this list is one more than the number of words to accommodate the maximum possible frequency.
For each word and its frequency from the
frequencyMap
:Add the word to the corresponding bucket (indexed by its frequency).
Initialize each bucket with a trie that stores words with the same frequency.
Next, iterate over
buckets
from the highest frequency to the lowest. For each nonempty trie:Retrieve all words stored in it.
If the number of retrieved words is less than
k
, add all of them totopK
and decrementk
by the number of added words.Otherwise, add only the top
k
words (sorted lexicographically) totopK
and terminate the loop.
Return the
topK
containing the topk
elements sorted according to their frequencies.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.