A dashboard job is given event-type IDs from a busy service and asked for the k hottest keys this window. The first version counted, then nested a scan: among unused uniques, which has the highest count, k times. A staging tenant with a dozen error codes returned before the page painted. A production window with tens of thousands of distinct IDs was still hunting the next hottest key when the request timed out.

Top K Frequent asks for the k values that appear most often. A hash table already gives counts in a pass. Nested “next unused max” uses those counts and still pays another scan per winner. A heap of size k keeps only the current winners and evicts the quietest.

This is an interview writeup, not a hashing or heap lecture. Those posts own buckets, collisions, and sift. Here we only care about counting, then keeping k winners.

The problem

Given an int[] nums and an int k, return the k values that appear most often. Assume k is at least 1 and at most the number of unique values. Order of the k answers does not matter.

nums = [7, 4, 7, 9, 7, 4], k = 2  →  [7, 4]    7 three times, 4 twice
nums = [18, 18, 18],       k = 1  →  [18]
nums = [5, 12, 5, 12],     k = 2  →  [5, 12]   both twice; either order

Note: Sorting every unique by frequency and slicing the first k is a legal middle path. It is not the usual interview answer when they hinted at a heap: you paid O(u log u) to rank keys you were going to throw away. A size-k heap ranks only against the current floor.

Scan for the next hottest unique is the honest brute force

Count somehow — a map is fine — then k times walk the remaining unique values and pick the unused key with the highest frequency. Correct. Slow in the unique count.

int[] topKFrequentScan(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) {
        freq.put(n, freq.getOrDefault(n, 0) + 1);
    }
    List<Integer> uniques = new ArrayList<>(freq.keySet());
    boolean[] used = new boolean[uniques.size()];
    int[] answer = new int[k];
    for (int slot = 0; slot < k; slot++) {
        int best = -1;
        for (int i = 0; i < uniques.size(); i++) {
            if (used[i]) {
                continue;
            }
            if (best < 0 || freq.get(uniques.get(i)) > freq.get(uniques.get(best))) {
                best = i;
            }
        }
        used[best] = true;
        answer[slot] = uniques.get(best);
    }
    return answer;
}

At a dozen keys this is a rounding error. At tens of thousands of distinct IDs you paid a nested hottest-scan for a question a size-k heap answers while it walks the map once: which k values won?

Count, then a min-heap of size k

Build the frequency map in one pass. Then walk each unique value. The heap is a min-heap on frequency, not on the value itself. Root is the quietest key you are currently keeping.

  • Offer the value.
  • If the heap now holds more than k keys, poll. That poll drops the quietest, so the remaining k are still the loudest seen so far.

You never restart a max-scan. You never sort the whole unique list. When the map walk finishes, the heap is the answer — drain it in any order.

nums = [7, 4, 7, 9, 7, 4]   k = 2

count:  7→3  4→2  9→1

offer 7  freq=3   heap [7]
offer 4  freq=2   heap [4, 7]        // 4 is quieter; root is 4
offer 9  freq=1   heap [9, 4, 7]     size 3 > k, poll 9
                  heap [4, 7]

answer [4, 7]   (order does not matter)

The Java is that walk. PriorityQueue is a min-heap; the comparator reads the map so two keys compare by how often they appeared:

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) {
        freq.put(n, freq.getOrDefault(n, 0) + 1);
    }
    PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(freq.get(a), freq.get(b)));
    for (int value : freq.keySet()) {
        heap.offer(value);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    int[] answer = new int[k];
    for (int i = 0; i < k; i++) {
        answer[i] = heap.poll();
    }
    return answer;
}

Time is expected O(n) then O(n log k) — count in one pass, then one offer (and maybe a poll) per unique key. Unique count is at most n, so the heap bill is O(n log k). Space is O(n) for the map. The heap holds at most k + 1 keys. Do not re-lecture sift or hash buckets at the whiteboard unless they ask.

Note: If they want linear time, bucket by frequency: an array of lists of length n + 1, index i holds values that appeared i times, then walk from the high end until you have k values. That is the O(n) answer. The heap is the usual board default when they said “heap” or k is tiny next to n.

Note: Return the values, not the frequencies. A missing comparator ranks the keys themselves, so you keep the k smallest numbers instead of the k loudest. k can equal the number of unique values — the heap never evicts, and that is still correct. Do not poll a heap you never filled.

What interviewers usually poke next

  • Linear time. Frequency buckets of length n + 1, walk from the high end. No heap. Same counts; a different way to pick the winners.
  • k = 1. After the map, one scan for the max frequency. A heap of size 1 is the same idea with extra ceremony; say you noticed.
  • Ties. If several values share a boundary frequency, any of the tied values is fine unless they ask for a specific tie-break.
  • Group Anagrams. That map hashes a signature so anagrams land in one list. This map hashes the value itself and then ranks by count. Same structure, different question.

You are done with this problem when you can say, out loud, why scanning for the next hottest unique is correct, why a size-k min-heap evicts the quietest instead of sorting every key, and why an array of frequency buckets is the linear follow-up.