#692 Top K Frequent Words

frequently reported atUber Bloomberg Amazon Google

the problem

In plain words

Given an array of words and an integer k, return the k most frequent words. List them from most to least frequent; words with the same frequency go in alphabetical (lexicographical) order.

in words = ["i","love","leetcode","i","love","coding"], k = 2

out ["i","love"]

"i" and "love" appear twice each; "i" comes first alphabetically.

in words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4

out ["the","is","sunny","day"]

Counts 4, 3, 2 and 1.

1 ≤ words.length ≤ 500
1 ≤ words[i].length ≤ 10, lowercase English letters
k is between 1 and the number of distinct words
Follow-up: O(n log k) time and O(n) extra space

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTop-k with a size-k heap Frequency counting Sort with a custom comparator

Count with a HashMap, then it's top-k under a two-key order: count high → low, then word A → Z. In a size-k min-heap flip both keys, so the weakest word — lowest count, later alphabetically — sits on top to be evicted.

solutions

From brute force to optimal

Sort the distinct words by (count descending, word ascending) and take the first k.

Count with merge(w, 1, Integer::sum).
Sort the keys with a two-key comparator.
Return the first k.

timeO(n + m log m)

m distinct words sorted; each comparison may compare strings of up to 10 letters.

spaceO(m)

The map and the key list.

javajava.util.*

1class Solution {2    public List<String> topKFrequent(String[] words, int k) {3        Map<String, Integer> count = new HashMap<>();4        for (String w : words) count.merge(w, 1, Integer::sum);5        List<String> unique = new ArrayList<>(count.keySet());6        unique.sort(Comparator.comparing((String w) -> count.get(w), Comparator.reverseOrder()) // more frequent first7                .thenComparing(Comparator.naturalOrder()));                                     // tie: A → Z8        return new ArrayList<>(unique.subList(0, k));9    }10}

Heap ordered by (count ascending, word descending) keeps the k best; poll them out and reverse.

Count.
Offer each distinct word; if size > k, poll the weakest.
Poll everything into a list (weakest first) and reverse it.

timeO(n + m log k)

m offers/polls on a heap of ≤ k + 1 — the follow-up's O(n log k).

spaceO(m + k)

The map plus the heap.

javajava.util.*

1class Solution {2    public List<String> topKFrequent(String[] words, int k) {3        Map<String, Integer> count = new HashMap<>();4        for (String w : words) count.merge(w, 1, Integer::sum);5        // root = the WEAKEST of the current top k: lowest count; for equal counts, the word later in A → Z6        PriorityQueue<String> heap = new PriorityQueue<>(7                Comparator.comparingInt((String w) -> count.get(w)).thenComparing(Comparator.reverseOrder()));8        for (String w : count.keySet()) {9            heap.offer(w);10            if (heap.size() > k) heap.poll();                 // evict the weakest11        }12        List<String> result = new ArrayList<>();13        while (!heap.isEmpty()) result.add(heap.poll());      // weakest first…14        Collections.reverse(result);                          // …so reverse: strongest first15        return result;16    }17}

in the room

How to say it in the interview

talk track

Say both sort keys out loud before coding: count high → low, then word A → Z.
For the heap, explain why the comparator is flipped (count ascending, word descending): the root must be the word you'd throw out first.
Remember to reverse the polled list at the end.

traps

Heap comparator with the word ascending: on ties the heap then evicts the alphabetically earlier word — the one you must keep.
Returning the polled order without reversing it — the answer comes out weakest first.
Comparing two Integer counts with == — it only works for cached values −128..127. Use equals or Integer.compare.

what they ask next

Follow-ups

Can buckets make it O(n)?

Bucket by count (a count is at most n), but each bucket still needs alphabetical order — sort inside the buckets or use a trie. With n ≤ 500 the heap is simpler.

Words arrive as a stream?

Keep the counting map plus a TreeSet ordered by (count, word): on each new word remove its old entry and add the new one in O(log m); the best k are at one end.

before you submit

Edge cases to test

All words tied: the answer is the first k words alphabetically.
A word and its prefix with equal counts, e.g. "a" and "aa": "a" comes first.
k = number of distinct words: return all of them, fully ordered.
A single word: return it.

practise next