Given an array of lowercase words and an integer k, return the k most frequent distinct words. Order the result by decreasing frequency. For equal frequencies, place the lexicographically smaller word first.
Example 1
Input: words = ["code", "tea", "code", "eat", "tea", "ant"], k = 3
Output: ["code", "tea", "ant"]
Explanation: "code" and "tea" both appear twice, so lexicographic order places "code" first. "ant" and "eat" both appear once, so "ant" receives the remaining position.
Example 2
Input: words = ["zoo", "ant", "zoo"], k = 1
Output: ["zoo"]
Explanation: "zoo" appears twice and has the greatest frequency.
Brute Force Approach
The simplest path is to rank every distinct word. A hash map first turns repeated words into word-frequency pairs, making every count easy to compare.
A custom sort then places larger counts first and resolves equal counts with lexicographic order. The first k entries form the required answer.
Algorithm
Begin with a frequency map so every repeated occurrence increases a single count instead of creating another candidate.
Scan the input array and update the matching map entry so every distinct word receives an exact frequency.
Copy all map keys into a list because only distinct words belong in the final ranking.
Sort the list by decreasing frequency so the most common words move toward the front.
Break equal-frequency ties by increasing lexicographic order so the required secondary ranking remains correct.
Keep the first
ksorted words because every later word has a lower rank than all selected candidates.Return the shortened list because the stored order already matches the required output order.
Dry Run
top-k-frequent-words-brute-force-logo-removed-final.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the k highest-ranked distinct words vector<string> topKFrequent(vector<string>& words, int k) { // Store one occurrence count for every word unordered_map<string, int> frequency; // Count every occurrence in the input array for (string word : words) { frequency[word]++; } // Copy distinct words for complete sorting vector<string> rankedWords; for (auto entry : frequency) { rankedWords.push_back(entry.first); } // Rank by count first and word order second sort(rankedWords.begin(), rankedWords.end(), [&](string first, string second) { // Larger counts must receive a better rank if (frequency[first] != frequency[second]) { return frequency[first] > frequency[second]; } // Smaller words win equal-frequency ties return first < second; }); // Only the first k ranked words are required rankedWords.resize(k); return rankedWords; }};// Driver codeint main() { vector<string> words = { "code", "tea", "code", "eat", "tea", "ant" }; int k = 3; Solution obj; vector<string> answer = obj.topKFrequent(words, k); for (string word : answer) { cout << word << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N + U log U), where N is the total number of words and U is the number of distinct words. Frequency counting takes O(N), while sorting the U distinct words takes O(U log U).
Space Complexity: O(U), because the frequency map and sorted list store up to U distinct words.
Optimal Approach
Full sorting ranks every distinct word, even though only k winners matter. A min-heap of size k keeps the current best candidates and removes the weakest candidate after every overflow.
The heap root represents the weakest candidate: lower frequency is weaker, and a lexicographically larger word is weaker during a tie. Reversing the removal order produces the final descending-frequency and ascending-lexicographic ranking.
Algorithm
Begin with a frequency map so every distinct word has one count for heap comparisons.
Keep a min-heap of at most
kwords so the weakest selected candidate always stays at the root.Treat a lower frequency as weaker because a more frequent word deserves a better output position.
Treat a lexicographically larger word as weaker during equal-frequency ties because a smaller word deserves the earlier position.
Insert every distinct word into the heap so every candidate receives a fair comparison against the current selection.
Remove the root after a heap overflow so only the best
kcandidates remain after all insertions.Pop all remaining words into an array and reverse the array because heap removal runs from weakest to strongest.
Return the reversed array because frequency and lexicographic order now match the required ranking.
Dry Run
Top K frequent Words Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution { // Orders the weakest candidate at the heap root struct Compare { bool operator()(pair<int, string> first, pair<int, string> second) { // Larger words are weaker during count ties if (first.first == second.first) { return first.second < second.second; } // Lower counts are weaker than higher counts return first.first > second.first; } };public: // Returns the k highest-ranked distinct words vector<string> topKFrequent(vector<string>& words, int k) { // Store one occurrence count for every word unordered_map<string, int> frequency; // Count every occurrence in the input array for (string word : words) { frequency[word]++; } // Keep the weakest selected word at the root priority_queue<pair<int, string>, vector<pair<int, string>>, Compare> minHeap; // Give every distinct word one heap comparison for (auto entry : frequency) { minHeap.push({entry.second, entry.first}); // Remove the weakest word after an overflow if ((int)minHeap.size() > k) { minHeap.pop(); } } // Read selected words from weakest to strongest vector<string> answer; while (!minHeap.empty()) { answer.push_back(minHeap.top().second); minHeap.pop(); } // Convert removal order into required rank order reverse(answer.begin(), answer.end()); return answer; }};// Driver codeint main() { vector<string> words = { "code", "tea", "code", "eat", "tea", "ant" }; int k = 3; Solution obj; vector<string> answer = obj.topKFrequent(words, k); for (string word : answer) { cout << word << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N + U log k), where N is the total number of words and U is the number of distinct words. Frequency counting takes O(N), while heap maintenance processes each distinct word with a heap of size at most k.
Space Complexity: O(U + k), because the frequency map stores counts for U distinct words and the heap stores at most k words.
Interview follow-up Questions
No. Every distinct word appears at most once because ranking happens over frequency-map keys.
Be the first to add a comment.