Free lesson · DSA Mastery - Interview Prep, End to End

Top K Frequent Words

Medium8 min readdsasorting-advanced-applications

Top K Frequent Words

Top K Frequent Words extends bucketing from a full sort to a selection problem: return the k most frequent words, breaking ties by alphabetical order. Frequencies bucket exactly as in the previous topic, but the alphabetical tiebreak adds a twist - within each frequency bucket, words must come out sorted lexicographically. This makes it a showcase of combining bucket sort with a secondary ordering rule, and it sets up the standard heap-based "top k" template you'll see again in the heaps section. We present the sort-everything baseline, a min-heap of size k, and the bucket-plus-sorted-buckets approach.

The insight: there are two orderings at play - primary by descending frequency, secondary by ascending word. Buckets handle the primary ordering in O(n); a small sort or careful comparator inside each bucket handles the secondary.

Interactive animation: Step through Top K Frequent Words yourself: every approach, frame by frame, on the lesson's own examples.

The Problem

Interactive animation: The lesson's example: the input, and the answer the algorithm has to produce.

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

Return the answer sorted by frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

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

Explanation: "i" and "love" are the two most frequent (2 each).
"i" comes before "love" alphabetically.

Example 2:

Input:  words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]

Explanation: Counts: the=4, is=3, sunny=2, day=1.

Constraints:

1 <= words.length <= 500
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
k is in the range [1, number of unique words].

Approaches Overview

#	Approach	Time	Space	Verdict
1	Count + full sort	O(n + m log m)	O(m)	Simple baseline
2	Count + min-heap of size k	O(n + m log k)	O(m + k)	Best when k << m
3	Count + buckets + sorted buckets	O(n + m log m)	O(n)	Bucket showcase

Here n = words.length, m = distinct words. The full sort orders all distinct words. The min-heap keeps only the top k. The bucket approach groups by frequency and sorts within buckets.

Approach 1: Count + Full Sort

The Idea

Count word frequencies. Collect distinct words and sort with a comparator: higher frequency first, and for equal frequency, lexicographically smaller word first. Take the first k. Clean and the easiest to get exactly right.

Logic Flowchart

graph TD
    A["count word frequencies"] --> B["collect distinct words"]
    B --> C["sort: count desc, then word asc"]
    C --> D["take first k"]
    D --> E["Return list"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the full-sort baseline. We count frequencies, then sort distinct words by descending count and ascending word for ties, and take the first k.

Code

public static List<String> topKFrequentSort(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) ->
        freq.get(a).equals(freq.get(b)) ? a.compareTo(b)        // tie: lexicographic
                                        : freq.get(b) - freq.get(a)); // else: count desc
    return candidates.subList(0, k);
}

This Java code counts word frequencies, sorts the distinct words by descending count with lexicographic tiebreak, and returns the first k.

Complexity

Time: O(n + m log m). Space: O(m). Fine for the small constraints here.

Approach 2: Count + Min-Heap of Size K - Best When k ≪ m

The Idea

Maintain a min-heap of size k ordered so the weakest candidate sits on top - meaning lower frequency is "smaller," and for equal frequency, the lexicographically larger word is "smaller" (so it's evicted first). Push each distinct word; if the heap exceeds k, pop the top. At the end the heap holds the top k, but in reverse order, so pop everything and reverse. Heap operations are O(log k), giving O(m log k).

Logic Flowchart

graph TD
    A["count frequencies"] --> B["min-heap: weakest on top"]
    B --> C["for each distinct word: push"]
    C --> D{"heap size > k?"}
    D -->|Yes| E["pop top (weakest)"]
    D -->|No| F["keep"]
    E --> G{"more words?"}
    F --> G
    G -->|Yes| C
    G -->|No| H["pop all into list, reverse"]
    H --> I["Return list"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the size-k min-heap. The weakest candidate sits on top so it is evicted when the heap exceeds k. After processing all words, the heap holds the top k, which we pop and reverse into the final order.

Code

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

    // min-heap: weakest on top -> lower freq smaller; tie -> lexicographically LARGER is smaller
    PriorityQueue<String> heap = new PriorityQueue<>((a, b) ->
        freq.get(a).equals(freq.get(b)) ? b.compareTo(a)
                                        : freq.get(a) - freq.get(b));
    for (String w : freq.keySet()) {
        heap.offer(w);
        if (heap.size() > k) heap.poll();          // drop the weakest
    }

    LinkedList<String> result = new LinkedList<>();
    while (!heap.isEmpty()) result.addFirst(heap.poll());   // reverse to strongest-first
    return result;
}

// Usage:
// topKFrequent(["i","love","leetcode","i","love","coding"], 2) -> ["i","love"]

This Java code counts frequencies and keeps a size-k min-heap whose top is the weakest candidate, evicting it whenever the heap grows past k. The heap is then drained from front, reversing the order so the most frequent words come first.

Step-by-Step Walkthrough

A frame-by-frame trace on words = ["i","love","leetcode","i","love","coding"], k = 2:

graph LR
    F0["count: i2 love2 leetcode1 coding1"]
    F1["push i(2); push love(2); size2"]
    F2["push leetcode(1): size3>2<br/>weakest = lowest freq → leetcode pop"]
    F3["push coding(1): size3>2<br/>weakest → coding pop"]
    F4["heap{i(2),love(2)} drain+reverse → [i, love]"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough counts i and love at two, leetcode and coding at one. The size-two min-heap keeps i and love, evicting the lower-frequency leetcode and coding. Draining and reversing gives i then love.

Result: ["i", "love"].

Interactive animation: Both rules, inside one comparator.

Complexity

Time: O(n + m log k). Space: O(m + k). Better than the full sort when k is much smaller than m.

Approach 3: Count + Buckets + Sorted Buckets (Bucket Showcase)

The Idea

Count frequencies, then place each word into bucket[f] indexed by frequency. Sort each bucket alphabetically (ascending) so ties resolve correctly. Scan buckets from highest frequency to lowest, appending words until you've collected k. Bucketing handles the primary order; the per-bucket sort handles the tiebreak.

Logic Flowchart

graph TD
    A["count frequencies"] --> B["bucket[f] = words with frequency f"]
    B --> C["sort each bucket lexicographically asc"]
    C --> D["for f = high to low: append words until k collected"]
    D --> E["Return first k"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the bucket showcase. Words are bucketed by frequency, each bucket is sorted alphabetically, and buckets are read from highest frequency down until k words are collected.

Code

public static List<String> topKFrequentBucket(String[] words, int k) {
    int n = words.length;
    Map<String, Integer> freq = new HashMap<>();
    for (String w : words) freq.merge(w, 1, Integer::sum);

    List<List<String>> bucket = new ArrayList<>();
    for (int i = 0; i <= n; i++) bucket.add(new ArrayList<>());
    for (Map.Entry<String, Integer> e : freq.entrySet()) bucket.get(e.getValue()).add(e.getKey());

    List<String> result = new ArrayList<>();
    for (int f = n; f >= 1 && result.size() < k; f--) {
        if (bucket.get(f).isEmpty()) continue;
        Collections.sort(bucket.get(f));            // lexicographic tiebreak within frequency
        for (String w : bucket.get(f)) {
            if (result.size() == k) break;
            result.add(w);
        }
    }
    return result;
}

This Java code buckets words by frequency, sorts each bucket alphabetically, and reads buckets from the highest frequency down, collecting words until it has k.

Complexity

Time: O(n + m log m) worst case from per-bucket sorting. Space: O(n). The bucketing is linear; sorting within buckets is the only log factor and only over distinct words.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Full sort	O(n + m log m)	O(m)	One comparator, take k	Simplest
Min-heap size k	O(n + m log k)	O(m + k)	Keep only top k	k ≪ m
Buckets + sort	O(n + m log m)	O(n)	Frequency index + tiebreak sort	Bucket practice

The min-heap is the standard interview answer for "top k" because it keeps the working set at size k - ideal when k is much smaller than the number of distinct items. The bucket version shines when you want the full ordering and k is large; its only log factor is the lexicographic tiebreak.

Interactive animation: Five against four is the heap losing on four words - and winning on four million.

Variations & Follow-ups

Why is the heap comparator "reversed" on the tiebreak?

The heap is a min-heap whose top is the candidate most deserving of eviction. Lower frequency should be evicted first (so lower freq = "smaller"); among equal frequencies, the alphabetically later word should be evicted first (so later word = "smaller"). That's why the tiebreak compares b to a rather than a to b. Draining and reversing then yields highest-frequency, alphabetically-first order.

Can you get true O(n) including the tiebreak?

Only if word comparisons are O(1), which they aren't in general (words have length up to L). With bucketing plus a tiebreak sort, the bound is O(n + m log m) on distinct words. For these constraints (n ≤ 500) any approach is instant; the asymptotic discussion matters at scale.

How does this generalize to "Top K Frequent Elements" (integers)?

Identical structure without the lexicographic tiebreak: count, bucket by frequency, read high-to-low for k items - a clean O(n) since integers need no secondary sort. That problem is the pure bucket "top k," and this one is its tie-broken sibling.

What about edge cases?

All same frequency: Pure alphabetical order decides the top k.
k equals number of distinct words: Return all, fully ordered.
Single word repeated: One bucket; that word is the answer.
Words of varying length: Lexicographic comparison handles prefixes ("is" before "island").

Common Interview Pitfalls

Forgetting the lexicographic tiebreak. Equal-frequency words must be alphabetical; many solutions miss this.
Getting the heap comparator backwards. The eviction order is the inverse of the output order.
Not reversing the heap output. A size-k min-heap yields weakest-first; reverse for the final answer.
Sizing buckets wrong. Indices must run 0..n since a word can appear up to n times.

Interactive animation: Order is part of the answer here, and the grader checks it.

Why This Problem Matters

Top K Frequent Words combines bucket sort for the primary key with a secondary ordering rule, and introduces the size-k heap "top k" template that recurs throughout the heaps section. Knowing when to keep only k items in a heap versus when to sort everything is a core efficiency judgment for selection problems.

The next topic, Maximum Gap, is the most surprising bucket-sort application: find the largest gap between consecutive elements of a sorted version of the array - in O(n) time, without fully sorting. The trick is the pigeonhole principle: distribute elements into evenly sized buckets so the maximum gap must occur between buckets, letting you skip intra-bucket comparisons entirely.

Back to DSA Mastery - Interview Prep, End to End