Solution: Top K Frequent Words

Let’s solve the Top K Frequent Words problem using the Trie pattern.

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:

  • 11 \leq words.length 100\leq 100

  • 11 \leq words[i].length 10\leq 10

  • 11 \leqk \leq 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 the words 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 to topK and decrement k by the number of added words.

    • Otherwise, add only the top k words (sorted lexicographically) to topK and terminate the loop.

  • Return the topK containing the top k 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.