grid47 Exploring patterns and algorithms
Aug 29, 2024
5 min read
Solution to LeetCode 692: Top K Frequent Words Problem
Given a list of words and an integer k, return the k most frequent words in the list. The words should be sorted by their frequency in descending order. If two words have the same frequency, they should be sorted lexicographically.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of words and an integer k.
Example: words = ["apple", "banana", "apple", "orange", "banana", "banana"], k = 2
Constraints:
• 1 <= words.length <= 500
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• k is in the range [1, the number of unique words]
Output: Return the k most frequent words sorted by frequency and lexicographical order.
Example: ["banana", "apple"]
Constraints:
Goal: The goal is to determine the k most frequent words from the given list and sort them by their frequency and lexicographical order.
Steps:
• Count the frequency of each word using a hash map.
• Sort the words first by frequency (descending) and then lexicographically.
• Return the first k words from the sorted list.
Goal: The input values are constrained as follows:
Steps:
• The number of words in the input list is between 1 and 500.
• The length of each word is between 1 and 10 characters.
• Words consist of lowercase English letters only.
• k is at most the number of unique words.
Assumptions:
• The input list is non-empty.
• There is at least one unique word in the list.
• Input: Example 1: words = ["apple", "banana", "apple", "orange", "banana", "banana"], k = 2
• Explanation: The words 'banana' and 'apple' are the two most frequent words. 'banana' appears 3 times and 'apple' appears 2 times, so they are returned as the result.
• Input: Example 2: words = ["cat", "dog", "bird", "dog", "dog", "bird", "bird"], k = 3
• Explanation: Both 'dog' and 'bird' appear 3 times, so they come first, followed by 'cat'. The result is ['dog', 'bird', 'cat'].
Approach: The solution involves counting the frequency of each word using a hash map and then sorting the words based on their frequency and lexicographical order.
Observations:
• We need to count the frequency of each word.
• Sorting needs to be done based on frequency and lexicographical order for ties.
• A priority queue or sorting could help in efficiently getting the top k frequent words.
Steps:
• Count the frequency of each word using an unordered map.
• Store the words in a priority queue that sorts by frequency and lexicographically for ties.
• Extract the top k words from the queue.
Empty Inputs:
• If words is an empty list, the result should be an empty list.
Large Inputs:
• Ensure the solution works within time constraints for large input sizes.
Special Values:
• If k equals the number of unique words, the function should return all the words.
Constraints:
• Ensure the solution handles edge cases like all words having the same frequency.
vector<string> topKFrequent(vector<string>& words, int k) {
This defines the `topKFrequent` function, which takes a vector of words and an integer 'k', and returns the top k most frequent words.
2 : Variable Initialization
unordered_map<string, int> mp;
This initializes an unordered map 'mp' to store the frequency of each word.
3 : Looping
for(string str: words)
This loop iterates over each word in the 'words' vector.
4 : Frequency Calculation
mp[str]++;
This increments the count for each word in the unordered map.
5 : Priority Queue Initialization
priority_queue<tup_t, vector<tup_t>, cmp> pq;
This initializes a priority queue 'pq' to store words and their frequencies, sorted by frequency using a custom comparator.
6 : Looping
for(autoit: mp) {
This loop iterates over the entries in the unordered map 'mp' (word-frequency pairs).
7 : Tuple Creation
auto tp = make_tuple(it.second, it.first);
This creates a tuple 'tp' containing the word's frequency (it.second) and the word itself (it.first).
8 : Priority Queue Insertion
pq.push(tp);
This inserts the tuple 'tp' (word and its frequency) into the priority queue.
9 : Vector Initialization
vector<string> ans;
This initializes an empty vector 'ans' to store the top k most frequent words.
10 : While Loop
while(k-->0) {
This while loop runs until the top k frequent words are found (decrements k each time).
11 : Priority Queue Access
auto e = pq.top();
This retrieves the top element (highest frequency) from the priority queue.
12 : Vector Insertion
ans.push_back(get<1>(e));
This adds the word (second element of the tuple) to the 'ans' vector.
13 : Priority Queue Pop
pq.pop();
This removes the top element (highest frequency) from the priority queue.
14 : Return Statement
return ans;
This returns the vector 'ans', which contains the top k most frequent words.
Best Case: O(n log k)
Average Case: O(n log k)
Worst Case: O(n log n)
Description: Sorting the words by frequency and lexicographical order takes O(n log n) time, but we are only interested in the top k words, so the best and average case is O(n log k).
Best Case: O(n)
Worst Case: O(n)
Description: We use extra space to store the frequency of each word, which is O(n), where n is the number of unique words.
