A search-ops dashboard is given last hour’s query tokens — or the error-code strings a gateway stamped on failed requests — and asked for the k hottest words this window. The first version counted, then sorted every unique token. A staging tenant with a dozen codes returned before the page painted. A production window with tens of thousands of distinct tokens was still ranking every rare misspelling when the request timed out.

Top K Frequent Words asks for the k words that appear most often, in a specific order. A hash table already gives counts in a pass. Top K Frequent Elements is the same count-then-heap shape for numbers: order of the k answers does not matter, and there is no lexicographic tie-break. Here the ranking is the question. A heap of size k keeps only the current winners and evicts the worst — quietest, or the later dictionary word when counts match.

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 ranking k words.

The problem

Given a String[] words and an int k, return the k most frequent words. Sort by frequency descending; ties break toward the lexicographically smaller word. Return those k words in that order. Assume k is at least 1 and at most the number of unique words.

words = ["timeout", "auth", "timeout", "disk", "auth", "timeout", "disk"], k = 2
→  ["timeout", "auth"]
timeout three times; auth and disk twice — auth is lexicographically smaller

words = ["retry", "retry", "retry"], k = 1
→  ["retry"]

words = ["cache", "hit", "cache", "miss"], k = 2
→  ["cache", "hit"]
cache twice; hit and miss once — hit is lexicographically smaller

Note: Sorting every unique by the ranking comparator 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 words you were going to throw away. A size-k heap ranks only against the current floor.

Count, then sort every unique is the honest brute force

Count in a map. Collect the unique words, sort them by frequency descending then lex ascending, and take the first k. Correct. Slow in the unique count.

List<String> topKFrequentSort(String[] words, int k) {
    Map<String, Integer> freq = new HashMap<>();
    for (String w : words) {
        freq.put(w, freq.getOrDefault(w, 0) + 1);
    }
    List<String> uniques = new ArrayList<>(freq.keySet());
    uniques.sort((a, b) -> {
        int fa = freq.get(a), fb = freq.get(b);
        if (fa != fb) {
            return Integer.compare(fb, fa);
        }
        return a.compareTo(b);
    });
    return new ArrayList<>(uniques.subList(0, k));
}

At a dozen tokens this is a rounding error. At tens of thousands of distinct error codes you paid a full unique-sort for a question a size-k heap answers while it walks the map once: which k words won, in that ranking?

Count, then a min-heap of size k

Build the frequency map in one pass. Then walk each unique word. PriorityQueue is a min-heap; the comparator defines worst. Root is the word you would drop first: lower frequency, or same frequency and lexicographically larger.

  • Offer the word.
  • If the heap now holds more than k words, poll. That poll drops the worst, so the remaining k are still the best seen so far.

“Best” is higher frequency, then lexicographically smaller. So the comparator puts the worse word toward the root: if frequencies differ, Integer.compare(freq(a), freq(b)) — smaller count is worse. If they match, b.compareTo(a) — reverse lex so the larger string sits toward the root and gets polled first on overflow.

You never sort the whole unique list. When the map walk finishes, the heap holds the k winners in worst-first order. Drain into a list and reverse so the answer is frequency descending, then lex ascending.

words = ["timeout", "auth", "timeout", "disk", "auth", "timeout", "disk"]   k = 2

count:  timeout→3  auth→2  disk→2

offer timeout  freq=3   heap [timeout]
offer auth     freq=2   heap [auth, timeout]           // auth is quieter; root is auth
offer disk     freq=2   heap [disk, auth, timeout]     size 3 > k
                        // disk and auth tie on count; disk is later in the dictionary
                        poll disk
                        heap [auth, timeout]

drain  auth, timeout    reverse → ["timeout", "auth"]

The Java is that walk. The comparator reads the map so two words compare by how often they appeared, then by reverse dictionary order:

List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> freq = new HashMap<>();
    for (String w : words) {
        freq.put(w, freq.getOrDefault(w, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
        int fa = freq.get(a), fb = freq.get(b);
        if (fa != fb) {
            return Integer.compare(fa, fb);
        }
        return b.compareTo(a);
    });
    for (String w : freq.keySet()) {
        heap.offer(w);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    List<String> answer = new ArrayList<>();
    while (!heap.isEmpty()) {
        answer.add(heap.poll());
    }
    Collections.reverse(answer);
    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 word. Unique count is at most n, so the heap bill is O(n log k). String compares on ties are proportional to word length, usually treated as constant at the board. Space is O(n) for the map. The heap holds at most k + 1 words. Do not re-lecture sift or hash buckets at the whiteboard unless they ask.

Note: Polling the heap is not the answer order. Root is the worst of the k winners. Drain then reverse. Returning the polls as they come is the usual miss — frequency ascending, and on a frequency tie the lexicographically larger word first.

Note: Top K Frequent Elements can drain in any order. This prompt cannot. A missing lex arm ranks only by count, so two words that share a boundary frequency come back in heap order instead of dictionary order. Flipping b.compareTo(a) keeps the later dictionary word on a tie — the opposite of the prompt. k can equal the number of unique words; the heap never evicts, and reverse is still required.

What interviewers usually poke next

  • k = 1. After the map, one scan for the max frequency, then the lexicographically smallest among ties. A heap of size 1 is the same idea with extra ceremony; say you noticed.
  • Bucket sort. An array of lists of length n + 1, index i holds words that appeared i times. Sort each occupied bucket lexicographically, then walk from the high end until you have k words. O(n) buckets plus string sorts — the linear-in-n follow-up when they drop the heap hint.
  • Return order. Drain then reverse. Polling without reverse is the usual miss. Do not sort the heap contents a second time unless they asked you to.
  • Numeric Top K. Top K Frequent Elements does not care about the order of the k answers and has no lex tie-break. Same count-then-heap, different ranking. Do not copy that solution here.
  • Kth Largest in a Stream. Size-k min-heap on value, a class that survives across adds. This heap ranks by count then lex, one shot.
  • Group Anagrams. That map hashes a signature so anagrams land in one list. This map hashes the word itself and then ranks by count. Same structure, different question.

You are done with this problem when you can say, out loud, why sorting every unique is correct, why a size-k min-heap’s root is the worst of the current winners (quietest, or the later dictionary word), and why you reverse after the drain.