Top K Frequent Elements
Mahabharata — The Most Celebrated Warriors — Finding the k Most Frequently Mentioned Names
k सबसे चर्चित — गणना करो, फिर शीर्ष k खोजो। लघु-ढेर आवृत्ति से — n log k में उत्तर॥
*k most frequent — count first, then find top k. Min-heap by frequency — answer in n log k.*
The Story
Find the k most frequently occurring elements in an array.
For `nums=[1,1,1,2,2,3]`, k=2: answer=[1,2] (1 appears 3 times, 2 appears 2 times).
**Step 1: Count frequencies** using a HashMap. **Step 2: Find top-k by frequency** using a min-heap of size k.
Min-heap ordered by FREQUENCY (ascending). Keep k elements with highest frequency: - For each (element, freq) pair: add to heap - If heap size > k: poll the minimum-frequency element (it's not in top-k) - After processing: heap contains exactly the top-k frequent elements
```java Map<Integer,Integer> freq = new HashMap<>(); for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]); // Min-heap by freq for (Map.Entry<Integer,Integer> e : freq.entrySet()) { pq.offer(new int[]{e.getKey(), e.getValue()}); if (pq.size() > k) pq.poll(); }
int[] result = new int[k]; for (int i = k-1; i >= 0; i--) result[i] = pq.poll()[0]; ```
**Bucket Sort Alternative (O(n)):** - Build frequency buckets: bucket[i] = list of nums with frequency i - Scan from bucket[n] down to bucket[1], collect k elements
Arjuna's commanders were ranked by how often they appeared in battle reports. A min-heap filtered the top-k by frequency in O(n log k).
The Sort-by-Frequency Approach
Count frequencies. Sort entries by frequency descending. Take first k. O(n log n).
public int[] topKFrequentBruteForce(int[] nums, int k) {
Map<Integer,Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
return freq.entrySet().stream()
.sorted((a,b)->b.getValue()-a.getValue())
.limit(k)
.mapToInt(Map.Entry::getKey)
.toArray();
}The Frequency-Min-Heap Wisdom
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // Min-heap by freq
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
pq.offer(new int[]{e.getKey(), e.getValue()});
if (pq.size() > k) pq.poll();
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) result[i] = pq.poll()[0];
return result;
}Step-by-Step Walkthrough
[1,2], k=2
Freq: {1:1, 2:1}
Add (1,1),(2,1): size=2≤2. No polling.
Return [1,2] ✅Deep Insight
**Bucket Sort O(n) approach:** ```java List<Integer>[] bucket = new List[n+1]; for (int i : freq.entrySet()) bucket[i.getValue()].add(i.getKey()); // Collect from high to low ``` This achieves O(n) but requires O(n) space and frequency range 1..n.
**When to use heap vs bucket sort:** - Heap: O(n log k). Better when k << n (e.g., k=10, n=10^6) - Bucket: O(n). Better when k is close to n and you need every element's frequency anyway
**Problem variants:** hp-4 is the same but with strings and lexicographic tiebreaking.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Count + sort all |
| Optimal | O(n log k) | O(n) | Count O(n) + heap O(n log k) |
Pattern Recognition
✅ Top-k by frequency: count first, then min-heap by freq ✅ Min-heap by frequency, size k ✅ Also solvable in O(n) with bucket sort ✅ Result order doesn't matter (problem says any order) **LeetCode Trigger Phrases:** → "top k frequent elements" → Find k most common values → Frequency-based k-selection
Bhagavad Gita 10.32
सर्गाणामादिरन्तश्च मध्यं चैवाहमर्जुन। अध्यात्मविद्या विद्यानां वादः प्रवदतामहम्॥
Among creations I am the beginning, end, and middle, O Arjuna. Among all knowledge I am the knowledge of the Self; among debaters I am the reasoning.
Connection: Among all elements in the array, the most frequent are those that resonate most powerfully through repetition. Their frequent appearance signals significance — like the most often-invoked names in the Mahabharata are those of the most important warriors. The min-heap's continuous filter identifies this elite set of k most resonant elements, their significance measured purely by the frequency of their manifestation.