Definition
- Frequency map – a hash map counting occurrences of each number in O(n) time.
- Min-heap keyed on frequency – the root holds the number with the lowest frequency among the K kept, making eviction of the weakest a single poll.
- Overflow eviction – when the heap exceeds size K after an offer, poll removes the least frequent number.
- O(n + d log K) time – counting is O(n), and each of the d distinct values costs at most O(log K) for a heap operation.
- Bucket sort alternative – when K is close to d, a bucket sort by frequency gives O(n) time by reading buckets from the high end.
At the National Bank of India, Rajesh wants to find the K merchant categories he spends on most often from a long transaction history. He first tallies how many times each category appears, then keeps a small bucket of the K most frequent categories, where the least frequent kept category sits on top so a more frequent one can push it out.
Understanding the Concepts
What is the Top K Frequent Numbers problem?
Given an unsorted array of numbers, find the K numbers that appear most frequently. If two numbers have the same frequency, either can be chosen. This combines frequency counting with the Top K Elements pattern.
package com.bank.analytics;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class TopKFrequent {
public static List<Integer> findTopKFrequent(int[] categories, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> freqMap = new HashMap<>();
for (int cat : categories) {
freqMap.merge(cat, 1, Integer::sum);
}
// Step 2: Min-heap of size K keyed on frequency
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
(a, b) -> freqMap.get(a) - freqMap.get(b)
);
for (int key : freqMap.keySet()) {
minHeap.offer(key);
if (minHeap.size() > k) {
minHeap.poll(); // evict least frequent
}
}
return new ArrayList<>(minHeap);
}
}
Why use a min-heap keyed on frequency?
The min-heap root holds the number with the lowest frequency among the K numbers currently in the heap. When a new number is offered and the heap size exceeds K, polling the root evicts the least frequent number, exactly the weakest candidate. This mirrors the Top K Largest pattern but with frequency as the comparison key instead of the value itself.
package com.bank.analytics;
public class FrequencyHeapDemo {
public static void trace() {
// Categories: [1, 1, 1, 2, 2, 3, 3, 3, 3, 4]
// Frequencies: {1:3, 2:2, 3:4, 4:1}
// K=2
// Offer 1 (freq=3): heap = [1] (size 1)
// Offer 2 (freq=2): heap = [2, 1] (size 2, root=2 freq=2)
// Offer 3 (freq=4): heap = [2, 1, 3] (size 3 > K=2)
// Poll: evict 2 (freq=2, least frequent)
// heap = [1, 3] (root=1 freq=3)
// Offer 4 (freq=1): heap = [4, 1, 3] (size 3 > K=2)
// Poll: evict 4 (freq=1, least frequent)
// heap = [1, 3] (root=1 freq=3)
// Final: top 2 frequent = [1 (freq 3), 3 (freq 4)]
}
}
How does frequency counting work?
A single pass over the array with map.merge(num, 1, Integer::sum) counts occurrences. This is O(n) time and O(d) space where d is the number of distinct values. The merge method is cleaner than the get-or-default-plus-put pattern.
package com.bank.analytics;
import java.util.HashMap;
import java.util.Map;
public class FrequencyCount {
public static void count() {
int[] transactions = {101, 202, 101, 303, 202, 101, 303, 303, 303};
Map<Integer, Integer> freq = new HashMap<>();
for (int txn : transactions) {
freq.merge(txn, 1, Integer::sum);
}
System.out.println(freq); // {101=3, 202=2, 303=4}
}
}
{101=3, 202=2, 303=4}
What is the bucket sort alternative?
When K is close to the number of distinct values, a bucket sort by frequency gives O(n) time. Create an array of buckets indexed by frequency (0 to n), place each number in its frequency bucket, then read from the highest bucket downward until K numbers are collected.
package com.bank.analytics;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class BucketSortFrequency {
@SuppressWarnings("unchecked")
public static List<Integer> findTopKBucket(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) freq.merge(num, 1, Integer::sum);
List<Integer>[] buckets = new List[nums.length + 1];
for (var entry : freq.entrySet()) {
int f = entry.getValue();
if (buckets[f] == null) buckets[f] = new ArrayList<>();
buckets[f].add(entry.getKey());
}
List<Integer> 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, Math.min(k, result.size()));
}
}
What is the time and space complexity?
| Approach | Time | Space | When to use |
|---|---|---|---|
| Frequency map + min-heap | O(n + d log K) | O(n + K) | K much smaller than d |
| Frequency map + bucket sort | O(n) | O(n) | K close to d |
| Sort by frequency | O(n + d log d) | O(n) | When simplicity matters |
What are edge cases?
Edge cases include K equal to zero (return empty), K equal to the number of distinct values (return all distinct values), all elements being the same (that one element is the only answer for K=1), and ties in frequency.
package com.bank.analytics;
import java.util.List;
public class EdgeCases {
public static void test() {
System.out.println(TopKFrequent.findTopKFrequent(new int[]{1,1,2,2,3}, 0)); // []
System.out.println(TopKFrequent.findTopKFrequent(new int[]{5,5,5}, 1)); // [5]
// Ties: {1:2, 2:2, 3:1}, K=1 -> either 1 or 2 is valid
}
}
What are common mistakes?
The most common mistake is ordering the heap by the number's value instead of its frequency. Another mistake is iterating over the original array instead of the frequency map's key set, which would offer duplicate entries to the heap.
package com.bank.analytics;
public class CommonMistakes {
// WRONG: heap ordered by value, not frequency
// PriorityQueue<Integer> heap = new PriorityQueue<>(); // orders by value!
// Fix: use comparator that compares freqMap.get(a) vs freqMap.get(b)
// WRONG: iterating over original array instead of distinct keys
// for (int num : nums) heap.offer(num); // offers duplicates!
// Fix: iterate over freqMap.keySet()
}
What should a senior engineer know?
A senior engineer should mention both the heap and bucket sort approaches and explain when each is better. The bucket sort approach is O(n) but uses more space for the bucket array. For streaming data where new numbers keep arriving, the heap approach is better because it can process incrementally. In a distributed system, each node computes local frequency maps and top-K heaps, and the coordinator merges them.
// Senior considerations:
// 1. Heap: O(n + d log K), better when K << d
// 2. Bucket sort: O(n), better when K close to d
// 3. Streaming: heap works incrementally
// 4. Distributed: local freq maps + local heaps, merge at coordinator
// 5. Approximate: count-min sketch for very large streams
Visual Overview
Two-Step Algorithm
===================
Input: [1, 1, 1, 2, 2, 3, 3, 3, 3, 4] K=2
Step 1: Frequency Map
─────────────────────
┌─────┬───────┐
│ Num │ Freq │
├─────┼───────┤
│ 1 │ 3 │
│ 2 │ 2 │
│ 3 │ 4 │
│ 4 │ 1 │
└─────┴───────┘
Step 2: Min-Heap (size K=2, keyed on freq)
──────────────────────────────────────────
Offer 1 (f=3): heap=[1]
Offer 2 (f=2): heap=[2, 1] root=2 (f=2)
Offer 3 (f=4): heap=[2, 1, 3] size>K → evict 2
heap=[1, 3] root=1 (f=3)
Offer 4 (f=1): heap=[4, 1, 3] size>K → evict 4
heap=[1, 3] root=1 (f=3)
Result: [1 (freq 3), 3 (freq 4)]
Bucket Sort Alternative
========================
Bucket index = frequency
┌───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │
│ │[4]│[2]│[1]│[3]│ ← numbers in each frequency bucket
└───┴───┴───┴───┴───┘
← read from right: bucket 4=[3], bucket 3=[1]
Top 2: [3, 1]
Key Takeaway
Top K Frequent Numbers combines frequency counting with the Top K Elements pattern. You first pass over the array and count how many times each number occurs in a hash map. Then you keep a min-heap of size K ordered by frequency, where the root is the least frequent of the numbers you are currently keeping. As you iterate over the distinct numbers, each one is offered to the heap, and when the heap grows beyond K, the root (least frequent) is evicted.
The overflow-then-evict step guarantees you always discard the weakest candidate, so after processing every distinct number the heap holds exactly the K most frequent ones. The counting is O(n) and the heap work is O(d log K) where d is the number of distinct values.
At the National Bank of India, Rajesh used this to find the K merchant categories a customer transacts in most often, powering a rewards recommendation from a long transaction history. He counted category frequencies once and kept a size-K min-heap keyed on frequency, evicting the least frequent kept category whenever a more frequent one arrived.
The senior-level insight is knowing when to switch tools: when K is close to the number of distinct values, a bucket sort by frequency achieves O(n) time by placing numbers in frequency-indexed buckets and reading from the high end. Mentioning both approaches shows depth.
Remember one sentence: count frequencies in a map, then keep a size-K min-heap keyed on frequency to hold the K most frequent numbers.
---