Log inSign up
mediumLeetCodeNot Started

Top K Frequent Words

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by frequency from highest to lowest. Words with the same frequency must be sorted in lexicographical order (ascending).

Example 1 · Example 1: Basic Words:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: i and love each appear 2 times. i comes before love alphabetically. Both appear more than other words (frequency 1).\n\nMin-Heap (Size 2):\n (freq 2, "love")\n /\n (freq 2, "i")

Example 2 · Example 2: Multiple Ties:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: the appears 4 times, is appears 3 times, sunny appears 2 times, day appears 1 time.

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]]

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master dual-key custom comparators in priority queues.
  • Understand why tie-breakers invert in a Min-Heap eviction strategy.
  • Implement the class cleanly across all 4 programming languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Top K items with primary and secondary sorting criteria (frequency desc, lexicographical asc).
  • K is much smaller than unique words count.
  • Custom comparator priority queue pattern.

Algorithmic Decision Tree:

  • Full sorting of unique words takes O(U log U).
  • Min-Heap of size K takes O(U log K) and bounds memory to O(K).

Connected Patterns:

Top K Frequent ElementsFrequency Sort

1. Brute Force — Full Sort on Unique Words

Intuition

Count frequencies of each word. Extract unique words into a list and sort with comparator: if count != count return count > count; else return word < word.

When to apply: When total words count is small (N <= 1000).

Algorithm

  1. Step 1: Count frequency of each word in hash map.
  2. Step 2: Collect unique words into a list.
  3. Step 3: Sort list using custom comparator: freq descending, word ascending.
  4. Step 4: Return first k words.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 vector<string> topKFrequent(vector<string>& words, int k) {
11 unordered_map<string, int> freq;
12 for (const string& w : words) freq[w]++;
13
14 vector<string> unique;
15 for (auto& [w, count] : freq) unique.push_back(w);
16
17 sort(unique.begin(), unique.end(), [&](const string& a, const string& b) {
18 if (freq[a] != freq[b]) return freq[a] > freq[b];
19 return a < b;
20 });
21
22 return vector<string>(unique.begin(), unique.begin() + k);
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<string> words = {"i","love","leetcode","i","love","coding"};
29 auto res = sol.topKFrequent(words, 2);
30 cout << "Top K Words (Brute Force): ";
31 for (const string& w : res) cout << w << " ";
32 cout << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N + U log U) — O(N + U log U) sorting unique words.
  • Space complexity: O(U) — O(U) storage for hash map and list.

Why Brute Force Doesn't Scale:

When U = 100,000 and K = 10, full sorting takes 100,000 * 17 ops, while Min-Heap takes 100,000 * 3.3 ops (5x faster) and uses O(K) heap memory.

Min-Heap runs in ~5ms for K = 10.

2. Better — Max-Heap of All Unique Words

Intuition

Push all unique words into a Max-Heap with priority: freq desc, word asc. Pop K times.

When to apply: When building full heap in O(U) and popping small K is preferred.

Algorithm

  1. Step 1: Compute frequencies using hash map.
  2. Step 2: Push all unique words into Max-Heap with custom comparator.
  3. Step 3: Pop K times and append to result list.
  4. Step 4: Return result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <queue>
6using namespace std;
7
8class Solution {
9public:
10 vector<string> topKFrequent(vector<string>& words, int k) {
11 unordered_map<string, int> freq;
12 for (const string& w : words) freq[w]++;
13
14 auto comp = [](const pair<int, string>& a, const pair<int, string>& b) {
15 if (a.first != b.first) return a.first < b.first;
16 return a.second > b.second; // smaller word has higher priority
17 };
18 priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(comp)> maxHeap(comp);
19
20 for (auto& [w, count] : freq) {
21 maxHeap.push({count, w});
22 }
23
24 vector<string> result;
25 for (int i = 0; i < k; i++) {
26 result.push_back(maxHeap.top().second);
27 maxHeap.pop();
28 }
29 return result;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<string> words = {"i","love","leetcode","i","love","coding"};
36 auto res = sol.topKFrequent(words, 2);
37 cout << "Top K Words (Max-Heap): ";
38 for (const string& w : res) cout << w << " ";
39 cout << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N + U + K log U) — O(N + U + K log U) time.
  • Space complexity: O(U) — O(U) heap space.

3. Optimal — Min-Heap of Size K with Inverted Comparator

Intuition

Keep a Min-Heap of size K. To evict correctly: lower frequency has higher eviction priority; if frequencies are equal, lexicographically LARGER word has higher eviction priority (it should be evicted before a smaller word). At the end, pop all K elements and reverse.

When to apply: Standard optimal solution with O(K) heap memory bound.

Algorithm

  1. Step 1: Compute frequencies using hash map.
  2. Step 2: Initialize Min-Heap comparing (count, word).
  3. Step 3: Comparator: if count differs, compare count; else compare words in reverse alphabetical order.
  4. Step 4: Push each unique word into heap. If size > k, pop root.
  5. Step 5: Collect all elements from heap and reverse. Return result.

Interactive Trace for Top K Frequent Words

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Process initial elements
Visual state
Values and pointers at this exact step
tree
Root: (1, 'coding')
1
Child: (1, 'leetcode')
1

Node order shown; add connections to display explicit tree edges.

root: w1
Check / comparison
Least frequent words sit at root.
Decision / next transition
Next higher frequency words will evict these candidates.
Why this step matters

Step 1: Process initial elements. Min-Heap holds [("coding", 1), ("leetcode", 1)]. Capacity k=2 reached.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <queue>
6#include <algorithm>
7using namespace std;
8
9class Solution {
10public:
11 vector<string> topKFrequent(vector<string>& words, int k) {
12 unordered_map<string, int> freq;
13 for (const string& w : words) freq[w]++;
14
15 auto comp = [](const pair<int, string>& a, const pair<int, string>& b) {
16 if (a.first != b.first) return a.first > b.first;
17 return a.second < b.second; // larger string evicted first
18 };
19 priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(comp)> minHeap(comp);
20
21 for (auto& [w, count] : freq) {
22 minHeap.push({count, w});
23 if ((int)minHeap.size() > k) {
24 minHeap.pop();
25 }
26 }
27
28 vector<string> result;
29 while (!minHeap.empty()) {
30 result.push_back(minHeap.top().second);
31 minHeap.pop();
32 }
33 reverse(result.begin(), result.end());
34 return result;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<string> words = {"i","love","leetcode","i","love","coding"};
41 auto res = sol.topKFrequent(words, 2);
42 cout << "Top K Words (Optimal): ";
43 for (const string& w : res) cout << w << " ";
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N + U log K) — O(N + U log K) time.
  • Space complexity: O(U) — O(U) hash map and heap space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Sort on Unique WordsO(N + U log U)O(U)Count frequencies in map. Sort unique words using custom comparator (freq desc, word asc). Take first k.Full sorting.
2.Better — Max-Heap of All Unique WordsO(N + U + K log U)O(U)Insert all unique words into Max-Heap. Pop K times.Heap holds U elements.
3.Optimal — Min-Heap of Size K with Reverse Tie-BreakerOptimalO(N + U log K)O(U)Maintain Min-Heap of size K. When size > K, evict element with lowest frequency or highest lexicographical order. Reverse result.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Incorrect tie-breaker comparator in Min-Heap

In Min-Heap, words with greater lexicographical order must be treated as smaller so they get popped first. Treating them normally pops the alphabetically smaller word!

Forgetting to reverse output

Min-Heap extracts from smallest to largest; the output must be reversed.

Comparing strings by length instead of alphabetical order

Lexicographical comparison compares character by character.

Crucial Edge Cases to Validate:

  • k == unique words count — Returns all words sorted by frequency and lexicographical order.
  • All words have equal frequency — Returns first k words in lexicographical order.
  • Single word array — Returns [words[0]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the inverted tie-breaker clearly — interviewers specifically look for candidates who understand why the comparator logic flips in a Min-Heap.
  2. Highlight the difference between Min-Heap (O(U log K)) and full sort (O(U log U)).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the string tie-breaker comparison in the Min-Heap be inverted (e.g., b.compareTo(a) instead of a.compareTo(b))?

Back to DSA Sheet