Top K Frequent Elements: HashMap Frequency Plus Min-Heap or Bucket Sort

• Step 1: Frequency map – count how often each element appears using a HashMap.
• Min-heap approach – a PriorityQueue of size K ordered by frequency ascending; poll the smallest when size > K. O(n log K).
• Bucket-sort approach – array of buckets indexed by frequency (0 to n); walk from the highest bucket down, collecting K elements. O(n).
• Trade-off – heap is simpler and streaming-friendly; buckets are linear but use O(n) extra space.
• Comparator – order by frequency ascending so the least frequent is on top and gets evicted first.

What is the Top K Frequent Elements problem?

Given an integer array and an integer K, return the K elements that appear most frequently. The answer may be returned in any order. The solution should be better than O(n log n) where possible.

At the National Bank of India, the teller app shows a quick-select menu of the K most common transaction amounts for faster entry.

Step 1: Build a frequency map

This step is always the same regardless of which selection method you use.

Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
    freq.merge(x, 1, Integer::sum);
}

This is O(n) time and O(n) space in the worst case (all distinct elements).

Approach A: Min-heap of size K

Maintain a min-heap (PriorityQueue) of size K, ordered by frequency ascending. Iterate through the map entries and offer each into the heap. When the heap exceeds K, poll the smallest.

package com.bank.analytics;

import java.util.*;

public class TopKFrequentHeap {

    public static List<Integer> topKFrequent(int[] amounts, int k) {
        // Step 1: frequency map
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : amounts) {
            freq.merge(x, 1, Integer::sum);
        }

        // Step 2: min-heap of size K
        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a, b) -> freq.get(a) - freq.get(b)  // ascending by frequency
        );

        for (int key : freq.keySet()) {
            heap.offer(key);
            if (heap.size() > k) {
                heap.poll();  // evict least frequent
            }
        }

        return new ArrayList<>(heap);
    }

    public static void main(String[] args) {
        int[] amounts = {500, 1000, 500, 200, 1000, 500, 200, 1000, 1000};
        System.out.println("Top 2: " + topKFrequent(amounts, 2));
    }
}

Top 2: [500, 1000]

Time: O(n log K). Space: O(n) for the map + O(K) for the heap.

Approach B: Bucket sort by frequency

Any element's frequency is between 1 and n. Create an array of lists (buckets) indexed by frequency. Place each element into its frequency bucket. Walk from the highest bucket downward, collecting elements until K are gathered.

package com.bank.analytics;

import java.util.*;

public class TopKFrequentBucket {

    public static List<Integer> topKFrequent(int[] amounts, int k) {
        // Step 1: frequency map
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : amounts) {
            freq.merge(x, 1, Integer::sum);
        }

        // Step 2: bucket sort by frequency
        @SuppressWarnings("unchecked")
        List<Integer>[] buckets = new ArrayList[amounts.length + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            buckets[e.getValue()].add(e.getKey());
        }

        // Step 3: collect from highest frequency
        List<Integer> result = new ArrayList<>();
        for (int f = buckets.length - 1; f >= 0 && result.size() < k; f--) {
            result.addAll(buckets[f]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] amounts = {500, 1000, 500, 200, 1000, 500, 200, 1000, 1000};
        System.out.println("Top 2: " + topKFrequent(amounts, 2));
    }
}

Top 2: [1000, 500]

Time: O(n). Space: O(n) for the map + O(n) for the buckets.

How do the two approaches compare?

| Aspect | Min-heap (size K) | Bucket sort |
|---|---|---|
| Time | O(n log K) | O(n) |
| Space | O(n + K) | O(n) |
| Streaming | Yes (elements can arrive one by one) | No (need full frequency map first) |
| When K is small | Very fast (log K is small) | Still O(n) setup |
| When K is close to n | O(n log n) | Still O(n) |
| Implementation | Simpler | Bucket array setup |

What is the common mistake with the heap comparator?

The comparator must order by frequency ascending so the least frequent element sits at the top and is evicted when the heap overflows. Reversing the comparator (descending) puts the most frequent at the top, and evicting it returns the K least frequent instead.

// Wrong: max-heap evicts the MOST frequent
new PriorityQueue<>((a, b) -> freq.get(b) - freq.get(a));

// Correct: min-heap evicts the LEAST frequent
new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));

What are the edge cases?

• K equals the number of distinct elements – return all distinct elements.
• K = 1 – return the single most frequent element.
• All elements are the same – only one distinct element; return it.
• All elements have the same frequency – any K of them are valid.
• K > distinct elements – return all distinct elements.

What about QuickSelect?

A third approach uses QuickSelect (partition-based selection) on the frequency values to find the K-th highest frequency in O(n) average time, then collect all elements with frequency at or above that threshold. This is O(n) average but O(n^2) worst case, and harder to implement correctly.

What should a senior engineer know?

In production, Pankaj would choose the min-heap for a streaming workload (transaction amounts arriving in real time) and bucket sort for a batch analytics report (fixed dataset, need fastest possible). The choice depends on whether the data arrives incrementally or as a batch.

What are common interview follow-up questions?

• Can you do it in O(n)? – Yes, bucket sort or QuickSelect.
• What if K changes? – With a heap, rebuild or resize. With buckets, just read more or fewer from the top.
• What about the K least frequent? – Reverse: use a max-heap or read from the lowest bucket.
• What about ties? – If multiple elements share the K-th frequency, any subset is acceptable.