Top K Frequent Words

MediumBucket Sort · Heap · Trie🧩 Bucket & Counting Sort LeetCode #692 ↗Updated Oct 30, 2026

Problem

Given an array of lowercase words and an integer k, return the k words that occur most often. Order the answer by frequency, highest first; words with equal frequency are ordered alphabetically.

Input[i,love,leetcode,i,love,coding], k=2Output[i,love]

Input[a,b,a,c,b,a], k=3Output[a,b,c]

1 ≤ n ≤ 500 · 1 ≤ word length ≤ 10, lowercase · 1 ≤ k ≤ #unique words · Follow-up: O(n log k) time.

Try it yourself

Java

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Count first; then it is a ranking problem with a two-key order (count desc, word asc). Counts are bounded by n, so words can be bucketed by count; a trie inside each bucket yields its words alphabetically without sorting.

PatternBucket & Counting Sort

Instinct Keys live in a small, known range (letters, frequencies 1..n, bounded values) - index an array by the key instead of comparing, and get O(n).

Memory hack Don't compare, just file it - every value walks straight to its own pigeonhole, then you read the shelves in order.

Open the Bucket & Counting Sort guide →

Approaches

Brute ForceCount + Sort All Unique Words

Time O(n + m log m)Space O(m)

Build a frequency map, then sort the m unique words with a comparator: higher count first, ties broken by compareTo. The first k entries are the answer.

Java

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap<>();
    for (String w : words) count.merge(w, 1, Integer::sum);
    List<String> cand = new ArrayList<>(count.keySet());
    cand.sort((a, b) -> count.get(a).equals(count.get(b))
            ? a.compareTo(b) : count.get(b) - count.get(a));
    return new ArrayList<>(cand.subList(0, k));
}

Short and clear, but sorts every word even when k is tiny.

BetterMin-Heap of Size k

Time O(n + m log k)Space O(m)

Keep a heap whose top is the weakest of the current top-k (lowest count; on ties, the alphabetically larger word). Push every word and pop when size exceeds k. Popping yields weakest-first, so reverse at the end.

Java

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap<>();
    for (String w : words) count.merge(w, 1, Integer::sum);
    PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
        int fa = count.get(a), fb = count.get(b);
        return fa != fb ? Integer.compare(fa, fb) : b.compareTo(a); // weakest on top
    });
    for (String w : count.keySet()) {
        heap.offer(w);
        if (heap.size() > k) heap.poll();
    }
    List<String> result = new ArrayList<>();
    while (!heap.isEmpty()) result.add(heap.poll());
    Collections.reverse(result);
    return result;
}

Meets the O(n log k) follow-up; the reversed tie-break is easy to get wrong.

OptimalBucket Sort by Count + Trie per Bucket

Time O(n · L)Space O(n · L)

Count c lies in [1, n], so put each word in bucket[c]. Each bucket is a trie; a pre-order DFS over children a..z emits its words alphabetically. Walk buckets from high to low until k words are collected. L = max word length (≤ 10).

Java

class Trie {
    Trie[] next = new Trie[26];
    String word;
}
public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap<>();
    for (String w : words) count.merge(w, 1, Integer::sum);
    Trie[] bucket = new Trie[words.length + 1];
    for (Map.Entry<String, Integer> e : count.entrySet()) {
        int f = e.getValue();
        if (bucket[f] == null) bucket[f] = new Trie();
        Trie node = bucket[f];
        for (char c : e.getKey().toCharArray()) {
            if (node.next[c - 'a'] == null) node.next[c - 'a'] = new Trie();
            node = node.next[c - 'a'];
        }
        node.word = e.getKey();
    }
    List<String> result = new ArrayList<>();
    for (int f = words.length; f > 0 && result.size() < k; f--) {
        if (bucket[f] != null) collect(bucket[f], result, k);
    }
    return result;
}
private void collect(Trie node, List<String> result, int k) {
    if (result.size() == k) return;
    if (node.word != null) result.add(node.word); // prefix comes first
    for (Trie child : node.next) if (child != null) collect(child, result, k);
}

Linear in total characters — no comparison sort at all.

Pro tip

Simpler variant: buckets of List<String>, sorting each bucket when reached — fine in practice, but O(m log m) if all counts tie.

At a glance

Level	Approach	Time	Space
Brute Force	Count + Sort All Unique Words	`O(n + m log m)`	`O(m)`
Better	Min-Heap of Size k	`O(n + m log k)`	`O(m)`
Optimal	Bucket Sort by Count + Trie per Bucket	`O(n · L)`	`O(n · L)`

Common pitfalls

Heap tie-break must be reversed (larger word on top) or the wrong word is evicted.
Comparing boxed Integers with == — fails above 127.
Forgetting to reverse the heap output (it comes out weakest first).

Interview tips

State the ordering rule precisely before coding the comparator.
Point out k ≤ m, so the heap is O(m log k) ≤ O(m log m).
Contrast with Top K Frequent Elements (347), where ties need no ordering.

Pattern

Top-k with bounded keys → size-k min-heap, or bucket sort when the key (a count) is ≤ n.

My notes saved in this browser