Definition
- Frequency counting – a single linear pass with
map.merge(element, 1, Integer::sum). - Min-heap selection – a
PriorityQueueof size K ordered by frequency; the root is the weakest leader, evicted when a higher count arrives. - Bucket sort selection – n+1 buckets indexed by count; elements dropped into their count bucket; scan from highest bucket down.
- Heap complexity – O(n + m log K) where m is distinct element count.
- Bucket complexity – O(n) total.
At the National Bank of India, the operations team wants the K most common transaction types. A clerk tallies every transaction, then either keeps a small tray of the K highest tallies (heap) or drops each type into a bucket labelled by its count and reads buckets from the top (bucket sort).
Understanding the Concepts
What is the problem?
Given an array of elements and a value K, return the K most frequent elements in any order. For example, in [1,1,1,2,2,3] with K=2, the answer is [1, 2].
At the National Bank of India, the dashboard shows the K most common transaction types each day.
How does the frequency counting work?
Map<String, Integer> freq = new HashMap<>();
for (String txn : transactions) {
freq.merge(txn, 1, Integer::sum);
}
This is O(n) and creates one entry per distinct element.
How does the min-heap selection work?
package com.bank.analytics;
import java.util.*;
public class TopKFrequentHeap {
public static List<String> topK(String[] transactions, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String txn : transactions) {
freq.merge(txn, 1, Integer::sum);
}
PriorityQueue<Map.Entry<String, Integer>> heap =
new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
for (Map.Entry<String, Integer> entry : freq.entrySet()) {
heap.offer(entry);
if (heap.size() > k) {
heap.poll();
}
}
List<String> result = new ArrayList<>();
while (!heap.isEmpty()) {
result.add(heap.poll().getKey());
}
return result;
}
public static void main(String[] args) {
String[] txns = {"UPI", "NEFT", "UPI", "IMPS", "UPI", "NEFT", "RTGS"};
System.out.println("Top 2: " + topK(txns, 2));
}
}
Top 2: [NEFT, UPI]
How does the bucket sort selection work?
package com.bank.analytics;
import java.util.*;
public class TopKFrequentBucket {
@SuppressWarnings("unchecked")
public static List<String> topK(String[] transactions, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String txn : transactions) {
freq.merge(txn, 1, Integer::sum);
}
List<String>[] buckets = new List[transactions.length + 1];
for (Map.Entry<String, Integer> entry : freq.entrySet()) {
int count = entry.getValue();
if (buckets[count] == null) buckets[count] = new ArrayList<>();
buckets[count].add(entry.getKey());
}
List<String> result = new ArrayList<>();
for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
if (buckets[i] != null) {
result.addAll(buckets[i]);
}
}
return result.subList(0, k);
}
public static void main(String[] args) {
String[] txns = {"UPI", "NEFT", "UPI", "IMPS", "UPI", "NEFT", "RTGS"};
System.out.println("Top 2 (bucket): " + topK(txns, 2));
}
}
Top 2 (bucket): [UPI, NEFT]
Why is bucket sort linear?
A frequency can be at most n (if every element is the same). So the bucket array has at most n+1 entries. Creating it is O(m), filling it is O(m), and scanning it is O(n). No log factor anywhere.
How do the two selection approaches compare?
| Approach | Counting | Selection | Total |
|---|---|---|---|
| Min-heap | O(n) | O(m log K) | O(n + m log K) |
| Bucket sort | O(n) | O(n) | O(n) |
| Full sort | O(n) | O(m log m) | O(n + m log m) |
What are common mistakes?
Using a max-heap, which evicts the most frequent element instead of the least frequent.
// Wrong: max-heap evicts the most frequent
new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
// Correct: min-heap evicts the least frequent
new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
What are the edge cases?
- K equals the number of distinct elements: return all distinct elements.
- All elements identical: the single element is the only answer for K=1.
- Ties: the problem says any order, so break ties arbitrarily.
What should a senior engineer know?
The insight is recognizing that frequencies are bounded by n, which makes bucket sort linear. Both approaches share the identical frequency map; they differ only in selection. Stating this trade-off clearly is the senior signal.
For streaming data, use the heap approach because it processes elements one at a time.
What are common interview follow-up questions?
- What if K is close to the number of distinct elements? (Bucket sort is better.)
- What if elements stream in? (Use heap, updating the frequency map on each arrival.)
- How do you handle ties? (Problem says any order; if not, add a secondary sort key.)
Visual Overview
Transactions: [UPI, NEFT, UPI, IMPS, UPI, NEFT, RTGS] K = 2
Phase 1: Frequency Map
UPI -> 3
NEFT -> 2
IMPS -> 1
RTGS -> 1
Phase 2a: Min-Heap (size K=2)
offer UPI(3) -> [UPI(3)]
offer NEFT(2) -> [NEFT(2), UPI(3)]
offer IMPS(1) -> size 3, poll IMPS(1) -> [NEFT(2), UPI(3)]
offer RTGS(1) -> size 3, poll RTGS(1) -> [NEFT(2), UPI(3)]
Result: [NEFT, UPI]
Phase 2b: Bucket Sort
bucket[3] = [UPI]
bucket[2] = [NEFT]
bucket[1] = [IMPS, RTGS]
Scan from top: UPI, NEFT -> collected 2 -> done
Result: [UPI, NEFT]
┌──────────────────────────────────────────────┐ │ Top K Frequent: Two Selection Methods │ ├──────────────────────────────────────────────┤ │ │ │ Phase 1: freq.merge(e, 1, sum) -> O(n) │ │ │ │ │ ▼ │ │ Phase 2a: Min-Heap Phase 2b: Buckets │ │ ┌────────────────┐ ┌────────────────┐ │ │ │ offer + poll │ │ bucket[count] │ │ │ │ when size > K │ │ scan high->low │ │ │ │ O(m log K) │ │ O(n) │ │ │ └────────────────┘ └────────────────┘ │ └──────────────────────────────────────────────┘
Key Takeaway
Top K Frequent Elements always starts with a linear frequency-map pass. The only decision is how to select the K highest counts. The min-heap keeps a heap of size K ordered by frequency, evicting the least frequent when the heap exceeds K. Bucket sort creates n+1 buckets indexed by count and scans from the top.
The heap runs in O(n + m log K) and is best for small K or streaming data. Bucket sort runs in O(n) because frequencies are bounded by n, and is best when K is large or latency matters. Both share the identical first step.
At the National Bank of India, the operations dashboard displayed the K most frequent transaction types. For large daily volumes, Rajesh used bucket sort for linear selection. The heap was the fallback for streaming scenarios.
The insight interviewers reward is recognizing that frequencies are bounded, which makes bucket sort linear and lets it beat the heap's log factor.
Remember one sentence: count with a HashMap, then select the top K with a min-heap or bucket sort by frequency.
---