Top K Frequent Words
Mahabharata — The Sacred Lexicon — Finding k Most Spoken Words in the Epic
k सबसे बोले शब्द — आवृत्ति में समान हों तो वर्णमाला से। लघु-ढेर की कला — दोहरी तुलना से॥
*k most spoken words — if tied in frequency, alphabetical order decides. The art of the min-heap — dual comparison.*
The Story
Find the k most frequent words. If two words have the same frequency, sort them lexicographically (alphabetically).
For `words=["i","love","leetcode","i","love","coding"]`, k=2: answer=["i","love"]. Freq: i:2, love:2, leetcode:1, coding:1. Top 2 by freq: "i" and "love" (tied at 2, i < love alphabetically).
**Same approach as hp-3, but with a tiebreaker:** Min-heap comparator: - Primary: ascending frequency (lower freq at top → gets evicted first) - Secondary: DESCENDING lexicographic (when frequencies equal, the lexicographically LARGER word is at top → gets evicted first, keeping smaller words)
Comparator: `(a,b) -> a[1]!=b[1] ? a[1]-b[1] : b[0].compareTo(a[0])` (where [0]=word, [1]=freq, stored as Object[])
```java PriorityQueue<String> pq = new PriorityQueue<>( (a,b) -> freq.get(a).equals(freq.get(b)) ? b.compareTo(a) : // Higher lex at top (to evict) freq.get(a)-freq.get(b) // Lower freq at top ); for (String w : freq.keySet()) { pq.offer(w); if (pq.size() > k) pq.poll(); } ```
When collecting results, reverse the order (heap gives lowest-priority first): ```java List<String> result = new LinkedList<>(); while (!pq.isEmpty()) result.add(0, pq.poll()); ```
The dual comparator is the key distinction from hp-3.
The Sort-with-Comparator Approach
Count, sort by (-freq, word), take k. O(n log n).
public List<String> topKFrequentBruteForce(String[] words, int k) {
Map<String,Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
return freq.keySet().stream()
.sorted((a,b) -> freq.get(a).equals(freq.get(b)) ?
a.compareTo(b) : freq.get(b)-freq.get(a))
.limit(k).collect(Collectors.toList());
}The Dual-Comparator Min-Heap Wisdom
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum);
PriorityQueue<String> pq = new PriorityQueue<>((a, b) ->
freq.get(a).equals(freq.get(b)) ?
b.compareTo(a) : // Same freq: larger lex at top (evict first)
freq.get(a) - freq.get(b) // Lower freq at top (evict first)
);
for (String w : freq.keySet()) {
pq.offer(w);
if (pq.size() > k) pq.poll();
}
LinkedList<String> result = new LinkedList<>();
while (!pq.isEmpty()) result.addFirst(pq.poll());
return result;
}Step-by-Step Walkthrough
["i","love","i","love","coding"], k=2 Freq: i:2, love:2, coding:1 Add coding: [coding] Add i: [coding,i] size=2≤2 Add love: [coding,i,love] size=3>2 Comparator: coding(1) vs i(2): coding has lower freq→ at top→ poll coding pq=[i,love] Result: poll love→addFirst→[love]; poll i→addFirst→[i,love] ✓
Deep Insight
**Dual comparator logic:** The min-heap keeps elements where the TOP element is the 'least desirable' candidate: - Lower frequency = less desirable (we want top-k by frequency) - Among same frequency: higher lexicographic = less desirable (we want lexicographically smaller)
So the top of the heap = element most likely to be evicted next = least frequent, or same freq but larger lex.
**Result reversal:** The heap pops in eviction order (least desirable first). We want the result in most-desirable-first order. Using `addFirst` (or reversing) corrects this.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Count + sort |
| Optimal | O(n log k) | O(n) | Count O(n) + heap O(n log k) |
Pattern Recognition
✅ Top-k by frequency with lexicographic tiebreaker ✅ Dual comparator: lower freq first; same freq → higher lex first ✅ Collect with addFirst(poll()) to reverse heap order ✅ hp-3 (integers) vs hp-4 (strings with tiebreaker) **LeetCode Trigger Phrases:** → "top k frequent words" → Frequency ranking with lexicographic tiebreaker → Multi-key comparator in heap
Bhagavad Gita 7.8
प्रणवः सर्ववेदेषु शब्दः खे पौरुषं नृषु।
Among all the Vedas I am the Om; among sounds I am the transcendental vibration; among humans I am human excellence.
Connection: Among all words in the epic, some resonate with greater frequency — repeated in key moments of wisdom or valor. But when two words resonate equally, the purer form (the simpler, lexicographically smaller word) takes precedence, just as the most essential sounds of the Vedas are also the most fundamental. The dual comparator in the heap embodies this priority: frequency first, purity of form (lexicographic order) second.