Top K Frequent Words (LC 692)

Pattern: Top K Elements
Difficulty: Medium
Key Concept: Count frequencies with a map, then use a size-k min-heap with a custom order so the root is always the worst kept candidate (lowest freq, then lexicographically largest tie-break); finally sort the k words for output.

Problem Statement

Given an array of strings words and an integer k, return the **k most frequent strings`.

Ordering rules

Higher frequency comes first.
If two words have the same frequency, the lexicographically smaller word comes first (e.g. "i" before "love").

Input / Output

Input: String[] words, int k.
Output: List<String> of length k satisfying the ordering rules above.

Example

words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Frequencies: i → 2, love → 2, leetcode → 1, coding → 1
Top 2 by frequency are i and love; tie-break alphabetical → ["i", "love"].

1. Algorithm & Pseudocode

Brute force

Count each word: Map<String, Integer>.
Collect (word, freq) pairs into a list.
Sort the list with comparator: descending frequency, then ascending word.
Take first k words.

Optimal

Count frequencies (same map).
Min-heap of size at most k storing words. Comparator defines “smaller” = worse candidate:
- Lower frequency is worse.
- Same frequency → lexicographically larger word is worse (so we keep "i" over "love" when both have freq 2).
For each distinct word, offer; if size > k, poll.
Drain heap to a list and sort with the output comparator: freq desc, word asc (heap order ≠ final answer order).

Pseudocode

freq = count words

heap = min-heap with compare(w1, w2):
    if freq[w1] != freq[w2]:
        return freq[w1] - freq[w2]          // smaller freq = worse = earlier in min-heap
    return w2.compareTo(w1)                 // same freq: larger word worse

for each word in distinct words:
    heap.push(word)
    if heap.size > k:
        heap.pop()

answer = heap to list
sort answer by: freq descending, then word ascending
return answer

2. Step-by-Step Analysis (Beginner-Friendly)

Why a map? You need counts; a single pass with getOrDefault or merge is O(n) for n tokens.
Why heap if we could sort all distinct words? Sorting U unique words is O(U log U). A heap over distinct words is O(U log k); when U is large and k is small, that wins.
Why min-heap “backwards” tie-break? The root must be the next word to evict when you have k + 1 candidates. Among same frequency, you evict the lexicographically larger word first so the smaller one survives in the top-k.
Why sort at the end? The heap only tracks which k words belong in the answer, not their presentation order. Final order is frequency descending, then alphabetical — so you sort the k items explicitly.
Comparator.comparingInt / thenComparing: Express the output sort readably: primary key reversed frequency, secondary key natural String order.

3. The Dry Run

Input: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2.

Step A — Frequency table

Word	Count
`i`	2
`love`	2
`leetcode`	1
`coding`	1

Step B — Min-heap (eviction = root)

Comparator (smaller = worse = polled first from a min-heap):

If freq(a) != freq(b) → Integer.compare(freq(a), freq(b)) (lower frequency is worse).
If tied → b.compareTo(a) (same frequency → lexicographically larger word is worse).

Processing order: Distinct words in first-seen order: i → love → leetcode → coding.

Step	Offer	Size after offer	Root = worst (next to evict if size > k)	`poll()`?	Heap after
1	`i`	1	`i` only	no	`{ i }`
2	`love`	2	`love` (freq tie; `"love"` > `"i"` lex → worse)	no	`{ i, love }`
3	`leetcode`	3	`leetcode` (freq 1 beats 2 for being worse)	yes	remove `leetcode` → `{ i, love }`
4	`coding`	3	`coding` (freq 1; worse than both freq-2 words)	yes	remove `coding` → `{ i, love }`

Why leetcode leaves before i or love: Frequency 1 is strictly “worse” than frequency 2 under the primary key, so any freq-1 word sits at the root while freq-2 words remain in the heap.

Step C — Final sort for output

Heap has i (2), love (2). Sort by freq desc, word asc → ["i", "love"].

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.merge(w, 1, Integer::sum);
        }

        List<String> candidates = new ArrayList<>(freq.keySet());
        candidates.sort((a, b) -> {
            int fa = freq.get(a);
            int fb = freq.get(b);
            if (fa != fb) {
                return Integer.compare(fb, fa); // higher freq first
            }
            return a.compareTo(b);             // alphabetical
        });

        return candidates.subList(0, k);
    }
}

Time: O(n + U log U) where U = distinct words.
Space: O(U) for the map and list.

Optimal

import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.merge(w, 1, Integer::sum);
        }

        PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
            int fa = freq.get(a);
            int 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> ans = new ArrayList<>(heap);
        ans.sort(Comparator
                .comparingInt((String w) -> freq.get(w)).reversed()
                .thenComparing(w -> w));

        return ans;
    }
}

Time: O(n + U log k) for counting + heap; plus O(k log k) final sort (small).
Space: O(U) for frequencies + O(k) heap.

5. The “Java vs. Others” Edge

Map.merge(w, 1, Integer::sum): Idiomatic frequency update in one line; computeIfAbsent + put is equally valid.
Comparator.comparingInt(...).reversed().thenComparing(w -> w): Readable final sort; matches problem statement order explicitly.
Heap comparator vs output comparator: Easy to invert; remember: heap order = “who gets evicted first” (worst), output order = “who prints first” (best).
C++: Often a struct with operator< or custom comparator for priority_queue; same two-stage logic (heap + sort).
Python: Typical trick is heapq with tuples (-freq, word) because min-heap on (-freq, word) pulls smallest freq first when negated — different idiom, same idea.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	`O(n + U log U)`	`O(U)`	Sort all distinct words by (freq ↓, word ↑).
Optimal	`O(n + U log k)`	`O(U)`	Map + size-k heap; final `O(k log k)` sort of `k` items.