Top K Frequent Words Solution In C++/Python/Java/JS
Problem Description
Given an array of strings words and an integer k, return the k most frequent strings.
Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.
Examples:
Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.
Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"],k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.
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[i]]
Brute Force Approach:
The brute force approach involves counting the frequency of each string, storing this information, and then sorting all the strings based on their frequencies and lexicographical order. Finally, we take the top k elements. This method is simple but not the most efficient, as it processes the entire dataset without optimization.
How to Do It?
- Count Frequencies: Use a map to tally how often each string appears in the array.
- Create a Vector of Pairs: Transform the map into a vector of pairs (string, frequency) to prepare for sorting.
- Sort with a Custom Comparator: Sort the vector using a comparator that prioritizes higher frequencies and resolves ties with lexicographical order.
- Primary Criterion: Sort by frequency in descending order (higher frequency first).
- Secondary Criterion: For strings with equal frequency, sort lexicographically (alphabetically, ascending).
In C++, the sort function expects a comparator that returns true if the first argument should come before the second in the sorted order.
For descending frequency, we return true when freq_a > freq_b.
For equal frequencies, we return true when string_a < string_b (lexicographical order).
The comparator is typically a lambda function or a separate function passed to sort.
- Extract Top k: Take the first k strings from the sorted vector.
Let's walk through an example:
Dry Run with Example:
Input: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
- Step 1: Count Frequencies
- unordered_map freq:
"i" -> 2
"love" -> 2
"leetcode" -> 1
"coding" -> 1 - Step 2: Create a Vector of Pairs
- vector<pair<string, int>> wordFreq = [("i", 2), ("love", 2), ("leetcode", 1), ("coding", 1)]
- Step 3: Sort with Comparator
- Initial Vector: [("i", 2), ("love", 2), ("leetcode", 1), ("coding", 1)].
- Comparator Logic:
Compare ("i", 2) vs ("love", 2): 2 = 2, "i" < "love" → true, no swap.
Compare ("love", 2) vs ("leetcode", 1): 2 > 1 → true, no swap.
Compare ("leetcode", 1) vs ("coding", 1): 1 = 1, "coding" < "leetcode" → true, swap. - After Sorting: [("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)]
"i" and "love" (freq 2) are first, with "i" before "love" (lexicographical).
"coding" and "leetcode" (freq 1) follow, with "coding" before "leetcode". - Step 4: Extract Top k
- k = 2 → ["i", "love"]
How to code it up:
Step 1: Count the Frequency of Each Word
Use an unordered_map<string, int> freq to store the frequency of each word in the given array words.
Iterate through words and update the count for each word.
Step 2: Store Frequencies in a Vector
Since we need to sort the words based on their frequency, we store them in a vector of pairs vector<pair<string, int>> wordFreq.
This will help us sort the words efficiently.
Step 3: Sort the Words by Frequency and Lexicographical Order
Sort the vector wordFreq using sort().
Sorting conditions:
If two words have different frequencies, sort by descending order of frequency.
If two words have the same frequency, sort them in lexicographical (dictionary) order.
Step 4: Extract the Top k Words
Create a result vector vector<string> result.
Extract the first k words from wordFreq and push them into result.
Step 5: Return the Result
Return the result vector, which contains the k most frequent words sorted by frequency and lexicographical order.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
// Step 1: Count frequency of words
unordered_map<string, int> freq;
for (string& word : words) {
freq[word]++;
}
// Step 2: Store word-frequency pairs in a vector
vector<pair<string, int>> wordFreq;
for (auto& entry : freq) {
wordFreq.push_back({entry.first, entry.second});
}
// Step 3: Sort the vector based on frequency and lexicographical order
sort(wordFreq.begin(), wordFreq.end(),
[](const pair<string, int>& a, const pair<string, int>& b) {
if (a.second != b.second) {
return a.second >
b.second; // Sort by frequency (descending)
}
return a.first < b.first; // Sort lexicographically
});
// Step 4: Extract top k frequent words
vector<string> result;
for (int i = 0; i < k && i < wordFreq.size(); i++) {
result.push_back(wordFreq[i].first);
}
// Step 5: Return the result
return result;
}
};2. Java Try on Compiler
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// Step 1: Count frequency of words
Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
freq.put(word, freq.getOrDefault(word, 0) + 1);
}
// Step 2: Store word-frequency pairs in a list
List<Map.Entry<String, Integer>> wordFreq = new ArrayList<>(freq.entrySet());
// Step 3: Sort the list based on frequency and lexicographical order
wordFreq.sort((a, b) -> {
if (!a.getValue().equals(b.getValue())) {
return b.getValue() - a.getValue(); // Sort by frequency (descending)
}
return a.getKey().compareTo(b.getKey()); // Sort lexicographically
});
// Step 4: Extract top k frequent words
List<String> result = new ArrayList<>();
for (int i = 0; i < k; i++) {
result.add(wordFreq.get(i).getKey());
}
// Step 5: Return the result
return result;
}
}3. Python Try on Compiler
class Solution(object):
def topKFrequent(self, words, k):
"""
:type words: List[str]
:type k: int
:rtype: List[str]
"""
# Step 1: Count frequency of words
freq = Counter(words)
# Step 2: Sort words first by frequency (descending) then lexicographically
sorted_words = sorted(freq.keys(), key=lambda word: (-freq[word], word))
# Step 3: Return the top k elements
return sorted_words[:k]
4. Javascript Try on Compiler
/**
* @param {string[]} words
* @param {number} k
* @return {string[]}
*/
var topKFrequent = function(words, k) {
// Step 1: Count frequency of words
let freq = new Map();
for (let word of words) {
freq.set(word, (freq.get(word) || 0) + 1);
}
// Step 2: Sort words based on frequency and lexicographical order
let sortedWords = Array.from(freq.keys()).sort((a, b) => {
if (freq.get(a) !== freq.get(b)) {
return freq.get(b) - freq.get(a); // Sort by frequency (descending)
}
return a.localeCompare(b); // Sort lexicographically
});
// Step 3: Return the top k elements
return sortedWords.slice(0, k);
};
Top K Frequent Words Complexity Analysis
Time complexity: O(n+ mlogm * L)
Step 1: Counting Frequencies
We iterate over the input vector words of size n (where n is the number of words). For each word, insertion or increment in the unordered_map takes O(1) average time. Total time: O(n).
Step 2: Creating the Vector of Pairs
We iterate over the unordered_map, which has m unique words (where m ≤ n).Pushing each pair into the vector takes O(1) per entry. Total time: O(m).
Step 3: Sorting the Vector
The vector wordFreq has m elements (number of unique words).
Sorting a vector of size m takes O(m log m) (comparison-based sorting).
Each comparison involves checking integers (O(1)) and comparing strings.
Lexicographical comparison of two strings takes O(L) on average, where L is the average string length.
Total time complexity: O(m log m * L).
Step 4: Extracting Top k Words
We iterate over at most k elements of the sorted vector and push each word into the result vector.
Copying a string into the result takes O(L) per word.
Total time: O(k * L).
Overall Time Complexity
Combining all steps: O(n + m + m log m * L + k * L).
Since m ≤ n and k ≤ m, the dominant term is typically the sorting step.
Simplified: O(n + m log m * L), where:
n is the total number of words.
m is the number of unique words.
L is the average length of the strings.
If L is considered a constant (e.g., in problems where string length is bounded), the time complexity simplifies further to O(n + m log m).
Space complexity: O(m*L)
Auxiliary Space Complexity:
Explanation: Unordered Map: Stores m unique words and their frequencies.
Each entry is a pair of a string (average length L) and an integer.
Space: O(m * L) for the strings + O(m) for the integers ≈ O(m * L).
Vector of Pairs: Stores m pairs of (string, int).
Total Space: O(m * L) for the strings + O(m) for the integers ≈ O(m * L).
Input space complexity: O(m * L).
The input is a vector words containing m strings, where each string has an average length of L.
- The total space required to store this input is O(m * L).
Is the brute force approach efficient?
In the brute force approach for finding the top k frequent words, we used a vector of word-frequency pairs and sorted it with a custom comparator based on frequency and lexicographical order. This takes O(m log m * L) time (where m is the number of unique words and L is the average word length), which is fine for the given constraints of 1 <= words.length <= 500 and 1 <= words[i].length <= 10.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Since m ≤ n (where n is the total number of words, up to 500), and L is small (up to 10), this comfortably avoids a Time Limit Exceeded (TLE) error, even for larger inputs like n = 10⁴.
Can we optimize it?
In the brute force approach for finding the top k frequent words, we counted frequencies and then sorted all unique words by frequency, which can feel like scanning the list multiple times—once to count and again to organize everything. This leads to a time complexity of O(n + m log m * L), where n is the total number of words, m is the unique words, and L is the average word length.it’s still not the best for larger inputs, as sorting everything can pile up operations and risk a Time Limit Exceeded (TLE) error if the scale grows.
A more efficient way to solve this problem is to store the frequency of words in a data structure that allows constant-time lookups, such as a hashmap. Instead of iterating through the array multiple times, we can precompute the frequency of each element in O(n) time and store it in a hashmap.
What is hashmap?
A map (or hash map) is a data structure that stores data in pairs, where each pair consists of a {key, value}. You can think of it like a dictionary: for each unique key, there is an associated value. It helps us quickly look up, add, or update values based on keys.
We need to select the words that appear most frequently from the given words array. To do this efficiently, we first count how often each word appears using a hashmap (like unordered_map in C++), where the key is the word and the value is its frequency. This gives us a quick way to know how many times each word shows up. Once we have these frequency counts, we need to find the top k most frequent words.
So, can you think of a data structure that helps us keep track of the top k elements?
Yes, you’re right! We could use something like a Heap or priority queue to keep track of elements.
What is Heap?
A heap is a specialized tree-based data structure that allows for efficient retrieval of the smallest (min-heap) or largest (max-heap) element in O(1) time. However, insertion and deletion operations take O(log k) time. In our case, a max-heap ensures that the most frequent elements remain at the top, allowing us to efficiently extract the k most frequent elements.
The idea behind using a max-heap is that it helps us efficiently manage all the words and their frequencies, keeping the most frequent ones readily accessible. We push each word and its frequency into the max-heap, and since it naturally prioritizes higher frequencies, the top of the heap always holds the most frequent word.
To get the k most frequent words, we simply pop the top element k times—no need to worry about size limits during insertion because we can extract exactly what we need at the end. This way, the max-heap gives us the top k words in descending order of frequency, making it easy to pull out the most frequent ones we’re looking for!
How to do it:
Step 1: Count the Words
First, we need to know how many times each word shows up. Imagine we’re tallying votes—every time we see a word, we add a tick next to it. A hashmap is perfect for this because it’s like a little notebook: the word is the name, and the number is how many votes it got. For our list, we’ll go through each word and count them up.
Step 2: Build a Max-Heap
Now, picture a podium where the most popular words stand tallest. A max-heap is like that—it keeps the word with the highest frequency at the top. We’ll take our word counts and toss them into this heap. If two words have the same frequency, we’ll break the tie by putting the one that comes first alphabetically lower down (smaller in lexicographical order), since the problem wants that.
Step 3: Grab the Top k
With the heap ready, it’s like picking the top 2 winners off the podium. We just pop the top word, add it to our answer, and repeat for k = 2. Since it’s a max-heap, they’ll come out in descending frequency order, exactly what we need!
Let's walk through an example:
Input: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Step 1: Count Frequencies
We go through the array and tally each word in the hashmap:
"i": Appears at index 0 and 3 → freq["i"] = 2
"love": Appears at index 1 and 4 → freq["love"] = 2
"leetcode": Appears at index 2 → freq["leetcode"] = 1
"coding": Appears at index 5 → freq["coding"] = 1
Hashmap after this step:
freq = { "i": 2,
"love": 2,
"leetcode": 1,
"coding": 1 }
Step 2: Build the Max-Heap
We push each pair into the max-heap. The comparator says: higher frequency wins, and for equal frequencies, the word that’s lexicographically smaller stays higher. Let’s add them one by one and see the heap:
Push {"i", 2}: Heap: [("i", 2)]
Push {"love", 2}: Both have frequency 2, so compare "i" vs "love".
"i" < "love", but comparator uses >, so "i" stays above "love".
Heap: [("i", 2), ("love", 2)].
Push {"leetcode", 1}:
Frequency 1 < 2, so it goes below.
Heap: [("i", 2), ("love", 2), ("leetcode", 1)]
Push {"coding", 1}:
Frequency 1 < 2, so it’s lower; compare with "leetcode".
"coding" < "leetcode", but it’s a max-heap, so it adjusts.
Heap: [("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)].
The heap keeps "i" at the top (frequency 2, lexicographically smallest), followed by "love", then "coding" and "leetcode" (both frequency 1, ordered lexicographically).
Step 3: Extract Top k = 2
Pop the top: Top is ("i", 2) → Add "i" to result.
Result: ["i"]
Heap: [("love", 2), ("coding", 1), ("leetcode", 1)]
Pop the top again:
Top is ("love", 2) → Add "love" to result.
Result: ["i", "love"]
Heap: [("coding", 1), ("leetcode", 1)]
We stop at k = 2. Final result: ["i", "love"].
How to code it up:
- Count Frequencies with a Hashmap
Use an unordered_map to store each word and its count.
Loop through the words vector and increment the count for each word. - Set Up a Max-Heap
Use a priority_queue with a custom comparator.
Make it a max-heap: higher frequency goes on top; for ties, lower lexicographical order wins (so we compare strings inversely).
- Extract Top k
Pop the top k elements from the heap into a vector.
Return that vector as the result.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
// step 1: count frequencies
unordered_map<string, int> freq;
for (string& word : words) {
freq[word]++;
}
// Step 2: Set up a max-heap
auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
if (a.second != b.second) {
return a.second < b.second;
}
// min lexicographical order for ties
return a.first > b.first;
};
priority_queue<pair<string, int>, vector<pair<string, int>>,
decltype(cmp)>
pq(cmp);
// Push all word-frequency pairs into the heap
for (auto& entry : freq) {
pq.push({entry.first, entry.second});
}
// Step 3: Extract top k elements
vector<string> result;
for (int i = 0; i < k && !pq.empty(); i++) {
result.push_back(pq.top().first);
pq.pop();
}
return result;
}
};2. Java Try on Compiler
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// Step 1: Count frequencies
HashMap<String, Integer> freq = new HashMap<>();
for (String word : words) {
freq.put(word, freq.getOrDefault(word, 0) + 1);
}
// Step 2: Set up a max-heap
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
(a, b) -> {
if (a.getValue() != b.getValue()) {
return b.getValue() - a.getValue(); // Max-heap by frequency
}
// min lexicographical order
return a.getKey().compareTo(b.getKey());
});
// Push all word-frequency pairs into the heap
for (Map.Entry<String, Integer> entry : freq.entrySet()) {
pq.offer(entry);
}
// Step 3: Extract top k elements
List<String> result = new ArrayList<>();
for (int i = 0; i < k && !pq.isEmpty(); i++) {
result.add(pq.poll().getKey());
}
return result;
}
}3. Python Try on Compiler
class Solution(object):
def topKFrequent(self, words, k):
# Step 1: Count frequencies
freq = Counter(words)
# Step 2: Use a list and sort to simulate max-heap (simpler for Python)
pq = [(count, word) for word, count in freq.items()]
# Sort by descending frequency, ascending word
pq.sort(key=lambda x: (-x[0], x[1]))
# Step 3: Extract top k elements
return [word for count, word in pq[:k]]4. Javascript Try on Compiler
/**
* @param {string[]} words
* @param {number} k
* @return {string[]}
*/
var topKFrequent = function (words, k) {
// Step 1: Count frequencies
const freq = {};
for (let word of words) {
freq[word] = (freq[word] || 0) + 1;
}
// Step 2: Convert to array and sort (simulating max-heap)
const pq = Object.entries(freq).sort((a, b) => {
if (b[1] !== a[1]) {
return b[1] - a[1]; // Max by frequency
}
return a[0].localeCompare(b[0]); // Min lexicographical order
});
// Step 3: Extract top k elements
const result = [];
for (let i = 0; i < k && i < pq.length; i++) {
result.push(pq[i][0]);
}
return result;
};Top K Frequent Words Complexity Analysis
Time complexity: O(mlogm)
Step 1: Counting Frequencies
We iterate over the input vector words of size n (total number of words).
For each word, we insert or update its count in an unordered_map. On average, hashmap operations (insert/update) take O(1) time, though worst-case is O(n) with collisions (rare with a good hash function).
step2: Building the max heap
We iterate over the unordered_map, which has m entries (number of unique words, where m ≤ n).
For each entry, we push a pair<string, int> into the priority_queue.
Pushing into a heap of size s takes O(log s) time. Since we push all m elements:
First push: O(1) (heap size 0 → 1).
Second push: O(log 1) (size 1 → 2).
Up to m-th push: O(log (m-1)).
Total time for m pushes: O(1 + log 1 + log 2 + ... + log (m-1)) = O(log (m!)). this simplifies to O(m log m).
String comparisons in the comparator (a.first > b.first) take O(L) time (where L is the average word length), but this is typically small and bounded (e.g., L ≤ 10 in constraints), so we treat it as a constant factor.
Total for this step: O(m log m).
Step 3: Extracting Top k
We pop the top element from the heap k times.
Each pop operation on a heap of size m (shrinking to m - k) takes O(log m) time to reheapify.
Total time: O(k log m).
Since k ≤ m, this is bounded by the heap size.
Overall Time Complexity:
O(n + m log m + k log m)
The dominant term is usually O(m log m) for building the heap,
since n ≥ m and k ≤ m.
Space complexity: O(m*L)
Auxiliary Space Complexity:
Explanation:
1.Hashmap (freq):
Stores m unique words and their frequencies.
Each key (string) takes O(L) space, and each value is O(1).
Total: O(m * L) for keys + O(m) for values ≈ O(m * L).
2.Max-Heap (pq):
Stores m pairs of {string, int}.
Each pair: O(L) for the string + O(1) for the int.
Total: O(m * L) for strings + O(m) for ints ≈ O(m * L).
Comparator (cmp):
Lambda function, stored once, negligible O(1) space.
Input space complexity: O(m * L).
The input is a vector words containing m strings, where each string has an average length of L.
- The total space required to store this input is O(m * L).
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Given an array of points where points[i] = [x i , y i ] represents a point on the X-Y plane and an integer k , return the k closest points to the origin (0, 0) .
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x `1 ` - x `2 `) 2 + (y `1 ` - y `2 `) 2 ).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).