Top K frequent words

Rank all unique words, return the first K

Given a list of words and a number K, return the K most frequent — with a tie-break: when two words appear equally often, the alphabetically smaller one ranks higher. So apple banana apple banana cat with K=3 gives apple, banana, cat (apple and banana tie at 2, apple wins the alphabet).

Count first, then rank

The input repeats words, so stage one is a HashMap<String,Integer> built in one O(N) pass — the same counting move as the earlier frequency problems. What's new is stage two: once you have word → count, you must rank the unique words by the two-key rule and slice off the top K.

The comparator is the algorithm

Don't treat the comparator as implementation trivia — it encodes the definition of "better." Compare two words: if their counts differ, the higher count wins; if they tie, the alphabetically smaller wins. In Java, since sort is ascending by comparator result, you reverse the frequency comparison but leave the word comparison natural.

uniqueWords.sort((a, b) -> {
    int fa = freq.get(a), fb = freq.get(b);
    if (fa != fb) return Integer.compare(fb, fa);  // freq DESC
    return a.compareTo(b);                        // word ASC
});

Count, sort, slice at K

Type words (space-separated) and dial K. Every unique word is counted and ranked by the two-key rule; bars show frequency. The top K sit above the dashed cutoff in teal; everything below is dropped. Watch ties resolve alphabetically.

Try dog cat bat dog cat bat (all tie → pure alphabetical) or z a z c b (one dominant word, then a three-way tie).

Where the tie-break earns its keep

For apple banana apple orange banana apple mango orange, K=3:

HashMap, then sort

import java.util.*;

static 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);

    List<String> uniq = new ArrayList<>(freq.keySet());
    uniq.sort((a, b) -> {
        int fa = freq.get(a), fb = freq.get(b);
        return fa != fb ? Integer.compare(fb, fa) : a.compareTo(b);
    });
    return new ArrayList<>(uniq.subList(0, k));
}

Counting is O(N); sorting the U unique words is O(U log U); total O(N + U log U), O(U) space. With N ≤ 1000 that's trivially fast — the simplest approach that comfortably fits the constraints is the right one. Java's declarative form works too: Comparator.comparingInt(freq::get).reversed().thenComparing(naturalOrder()).

Keep only K, evict the worst

If unique words number in the millions but K is tiny, sorting everything is wasteful. Instead keep a size-K min-heap whose root is the worst currently-selected word. Each new word is offered; if the heap exceeds K, poll the root. That's O(U log K) — better when K ≪ U.

Why not a TreeMap, a set, or map order?

Frequency map, then whatever the question needs

This is the fourth question in the set built on a frequency map — and it shows the split cleanly. Stage one is always "what do I need to know about each distinct value?" Here: its count. Stage two is dictated by the exact wording:

Reconstruct it, don't memorize it

1. I need the K most frequent words → first I need every word's count.
2. Build word → count with a HashMap in one pass.
3. Now rank the unique words: higher frequency first.
4. On a tie, alphabetically smaller first.
5. Encode both rules in a comparator, sort, take the first K.