Solution Approach
Solution Overview
There are 3 main approaches to solve this problem:
- Brute Force Approach - Complex approach
- Heap (Priority Queue) Approach - Complex approach
- Bucket Sort Approach - Complex approach
Approach 1: Brute Force Approach
Let's start by understanding the problem: we need to find the k most frequent words in an array, with a specific sorting order.
Thinking Process: The most straightforward approach is to count the frequency of each word, sort all words by their frequencies, and then return the top k words.
First, we use a hash map to count the frequency of each word in the array. Then, we create a list of all unique words and sort them according to the problem's requirements: by frequency in descending order, and if frequencies are equal, by alphabetical order. Finally, we return the first k words from the sorted list.
Intuition: This approach directly follows the problem statement. We count frequencies, sort based on those frequencies and alphabetical order, and then return the top k words.
Algorithm:
- Create a hash map to store the frequency of each word in the array.
- Iterate through the array and count the frequency of each word.
- Create a list of all unique words from the hash map.
- Sort the list of words based on their frequencies in descending order, and if frequencies are equal, by alphabetical order.
- Return the first k words from the sorted list.
Time Complexity:
Where n is the number of unique words. Counting frequencies takes O(m) time where m is the length of the input array. Sorting takes O(n log n) time, and returning the top k words takes O(k) time. The overall time complexity is dominated by the sorting step, which is O(n log n).
Space Complexity:
We use a hash map to store word frequencies, which takes O(n) space where n is the number of unique words. We also need O(n) space for the list of unique words. The overall space complexity is O(n).
Approach 2: Heap (Priority Queue) Approach
We can optimize the previous approach by using a heap (priority queue) to find the k most frequent words.
Thinking Process: Instead of sorting all words, we can use a min heap of size k to keep track of the k most frequent words. We first count the frequency of each word using a hash map. Then, we iterate through all unique words and maintain a min heap of size k, where words are ordered by their frequencies (and alphabetically if frequencies are equal).
For each word, we add it to the heap. If the heap size exceeds k, we remove the word with the lowest frequency (or highest alphabetical order if frequencies are equal). After processing all words, the heap contains the k most frequent words.
Intuition: A min heap of size k allows us to efficiently find the k largest elements in a collection. By maintaining a heap of size k, we avoid sorting all words, which is more efficient when k is much smaller than the number of unique words.
Algorithm:
- Create a hash map to store the frequency of each word in the array.
- Iterate through the array and count the frequency of each word.
- Create a min heap of size k, where words are ordered by their frequencies (and alphabetically if frequencies are equal).
- Iterate through all unique words:
- a. Add the word to the heap.
- b. If the heap size exceeds k, remove the word with the lowest frequency (or highest alphabetical order if frequencies are equal).
- Extract words from the heap in reverse order to get the k most frequent words sorted by frequency (and alphabetically if frequencies are equal).
Time Complexity:
Where n is the number of unique words and k is the number of words to return. Counting frequencies takes O(m) time where m is the length of the input array. Adding each word to the heap takes O(log k) time, and we do this for n words, resulting in O(n log k) time. Extracting k words from the heap takes O(k log k) time. The overall time complexity is O(m + n log k + k log k), which simplifies to O(m + n log k) since k ≤ n.
Space Complexity:
We use a hash map to store word frequencies, which takes O(n) space where n is the number of unique words. We also need O(k) space for the heap. The overall space complexity is O(n + k), which simplifies to O(n) since k ≤ n.
Approach 3: Bucket Sort Approach
Another approach is to use bucket sort to find the k most frequent words.
Thinking Process: Since the frequency of a word is at most the length of the input array, we can use an array of buckets where each bucket corresponds to a frequency. We place words with the same frequency in the same bucket, sorted alphabetically.
After placing all words in their respective buckets, we iterate through the buckets from highest frequency to lowest and collect the k most frequent words.
Intuition: Bucket sort is more efficient than general sorting algorithms when the range of values to be sorted is limited, which is the case here. By using buckets, we can avoid comparing frequencies during the sorting process.
Algorithm:
- Create a hash map to store the frequency of each word in the array.
- Iterate through the array and count the frequency of each word.
- Create an array of buckets where each bucket corresponds to a frequency.
- Place words with the same frequency in the same bucket, sorted alphabetically.
- Iterate through the buckets from highest frequency to lowest:
- a. For each bucket, add words to the result list in alphabetical order.
- b. Stop when we have collected k words.
- Return the result list.
Time Complexity:
Where m is the length of the input array. Counting frequencies takes O(m) time. Creating buckets takes O(n) time where n is the number of unique words. Sorting words within each bucket takes O(n log n) time in the worst case, but since the number of words in each bucket is typically small, this is often closer to O(n). Collecting the k most frequent words takes O(k) time. The overall time complexity is O(m + n + n log n + k), which simplifies to O(m + n log n).
Space Complexity:
We use a hash map to store word frequencies, which takes O(n) space where n is the number of unique words. We also need O(m) space for the buckets in the worst case. The overall space complexity is O(n + m), which simplifies to O(m) since n ≤ m.
Pseudocode
1234567891011121314function topKFrequent(words, k): // Count frequency of each word freq = new HashMap() for each word in words: freq[word] = freq[word] + 1 or 1 if word not in freq // Create list of all unique words uniqueWords = list of keys in freq // Sort words by frequency (descending) and alphabetically (ascending) sort uniqueWords by (-freq[word], word) // Return top k words return uniqueWords[0:k]String Problems
Learning Objective
Understand different approaches to solve the word frequency analyzer problem and analyze their efficiency.
Solution Approaches
Approach 1: Brute Force Approach
Let's start by understanding the problem: we need to find the k most frequent words in an array, with a specific sorting order.
Thinking Process: The most straightforward approach is to count the frequency of each word, sort all words by their frequencies, and then return the top k words.
First, we use a hash map to count the frequency of each word in the array. Then, we create a list of all unique words and sort them according to the problem's requirements: by frequency in descending order, and if frequencies are equal, by alphabetical order. Finally, we return the first k words from the sorted list.
Intuition: This approach directly follows the problem statement. We count frequencies, sort based on those frequencies and alphabetical order, and then return the top k words.
Algorithm:
- Create a hash map to store the frequency of each word in the array.
- Iterate through the array and count the frequency of each word.
- Create a list of all unique words from the hash map.
- Sort the list of words based on their frequencies in descending order, and if frequencies are equal, by alphabetical order.
- Return the first k words from the sorted list.
Approach 2: Heap (Priority Queue) Approach
We can optimize the previous approach by using a heap (priority queue) to find the k most frequent words.
Thinking Process: Instead of sorting all words, we can use a min heap of size k to keep track of the k most frequent words. We first count the frequency of each word using a hash map. Then, we iterate through all unique words and maintain a min heap of size k, where words are ordered by their frequencies (and alphabetically if frequencies are equal).
For each word, we add it to the heap. If the heap size exceeds k, we remove the word with the lowest frequency (or highest alphabetical order if frequencies are equal). After processing all words, the heap contains the k most frequent words.
Intuition: A min heap of size k allows us to efficiently find the k largest elements in a collection. By maintaining a heap of size k, we avoid sorting all words, which is more efficient when k is much smaller than the number of unique words.
Algorithm:
- Create a hash map to store the frequency of each word in the array.
- Iterate through the array and count the frequency of each word.
- Create a min heap of size k, where words are ordered by their frequencies (and alphabetically if frequencies are equal).
- Iterate through all unique words:
- a. Add the word to the heap.
- b. If the heap size exceeds k, remove the word with the lowest frequency (or highest alphabetical order if frequencies are equal).
- Extract words from the heap in reverse order to get the k most frequent words sorted by frequency (and alphabetically if frequencies are equal).
Approach 3: Bucket Sort Approach
Another approach is to use bucket sort to find the k most frequent words.
Thinking Process: Since the frequency of a word is at most the length of the input array, we can use an array of buckets where each bucket corresponds to a frequency. We place words with the same frequency in the same bucket, sorted alphabetically.
After placing all words in their respective buckets, we iterate through the buckets from highest frequency to lowest and collect the k most frequent words.
Intuition: Bucket sort is more efficient than general sorting algorithms when the range of values to be sorted is limited, which is the case here. By using buckets, we can avoid comparing frequencies during the sorting process.
Algorithm:
- Create a hash map to store the frequency of each word in the array.
- Iterate through the array and count the frequency of each word.
- Create an array of buckets where each bucket corresponds to a frequency.
- Place words with the same frequency in the same bucket, sorted alphabetically.
- Iterate through the buckets from highest frequency to lowest:
- a. For each bucket, add words to the result list in alphabetical order.
- b. Stop when we have collected k words.
- Return the result list.
Complexity Analysis
Brute Force Approach Approach
Time Complexity
Where n is the number of unique words. Counting frequencies takes O(m) time where m is the length of the input array. Sorting takes O(n log n) time, and returning the top k words takes O(k) time. The overall time complexity is dominated by the sorting step, which is O(n log n).
Space Complexity
We use a hash map to store word frequencies, which takes O(n) space where n is the number of unique words. We also need O(n) space for the list of unique words. The overall space complexity is O(n).
Heap (Priority Queue) Approach Approach
Time Complexity
Where n is the number of unique words and k is the number of words to return. Counting frequencies takes O(m) time where m is the length of the input array. Adding each word to the heap takes O(log k) time, and we do this for n words, resulting in O(n log k) time. Extracting k words from the heap takes O(k log k) time. The overall time complexity is O(m + n log k + k log k), which simplifies to O(m + n log k) since k ≤ n.
Space Complexity
We use a hash map to store word frequencies, which takes O(n) space where n is the number of unique words. We also need O(k) space for the heap. The overall space complexity is O(n + k), which simplifies to O(n) since k ≤ n.
Bucket Sort Approach Approach
Time Complexity
Where m is the length of the input array. Counting frequencies takes O(m) time. Creating buckets takes O(n) time where n is the number of unique words. Sorting words within each bucket takes O(n log n) time in the worst case, but since the number of words in each bucket is typically small, this is often closer to O(n). Collecting the k most frequent words takes O(k) time. The overall time complexity is O(m + n + n log n + k), which simplifies to O(m + n log n).
Space Complexity
We use a hash map to store word frequencies, which takes O(n) space where n is the number of unique words. We also need O(m) space for the buckets in the worst case. The overall space complexity is O(n + m), which simplifies to O(m) since n ≤ m.
Pseudocode
Brute Force Approach Approach
1234567891011121314function topKFrequent(words, k): // Count frequency of each word freq = new HashMap() for each word in words: freq[word] = freq[word] + 1 or 1 if word not in freq // Create list of all unique words uniqueWords = list of keys in freq // Sort words by frequency (descending) and alphabetically (ascending) sort uniqueWords by (-freq[word], word) // Return top k words return uniqueWords[0:k]Heap (Priority Queue) Approach Approach
123456789101112131415161718192021function topKFrequent(words, k): // Count frequency of each word freq = new HashMap() for each word in words: freq[word] = freq[word] + 1 or 1 if word not in freq // Create min heap of size k heap = new MinHeap() for each word in freq: // Add word to heap heap.add((freq[word], word)) // If heap size exceeds k, remove word with lowest frequency if heap.size() > k: heap.poll() // Extract words from heap in reverse order result = new List() while heap is not empty: result.add(heap.poll()[1]) return result in reverse orderBucket Sort Approach Approach
12345678910111213141516171819202122232425262728function topKFrequent(words, k): // Count frequency of each word freq = new HashMap() for each word in words: freq[word] = freq[word] + 1 or 1 if word not in freq // Create buckets buckets = array of size words.length + 1 for each word in freq: if buckets[freq[word]] is null: buckets[freq[word]] = new List() buckets[freq[word]].add(word) // Sort words in each bucket alphabetically for each bucket in buckets: if bucket is not null: sort bucket alphabetically // Collect top k words result = new List() for i from buckets.length - 1 down to 0: if buckets[i] is not null: for each word in buckets[i]: result.add(word) if result.size() == k: return result return result