10  Top K Frequent Words

Rank 8 · Pattern: count, then sort distinct values · Target: \(O(n + u\log u)\) time

10.1 Problem definition

Given an array of words and an integer k, return the k most frequent distinct words. Order them by decreasing frequency, with lexicographically smaller words first when frequencies tie.

10.2 Clarifying questions

  1. Does each distinct word appear at most once in the result?
  2. How should results be ordered, including words tied in frequency?
  3. Is word matching case-sensitive, and which lexicographic ordering should I use?
  4. What range of k is guaranteed?
  5. Can the array or any word be null? Are empty strings allowed as words?

10.3 Sample answers

  1. Yes. Return k distinct words; repeated occurrences only increase a word’s frequency.
  2. Order by decreasing frequency, then lexicographically ascending for ties.
  3. Matching is case-sensitive. Use the language’s ordinary string ordering; the examples use ASCII words, for which all three implementations agree.
  4. k is at least 1 and at most the number of distinct words.
  5. The array and its words are non-null. An empty string may be treated as an ordinary word.

10.4 Data structures and APIs

Each implementation counts words in a map, sorts only the distinct keys by a two-part key, and returns the first k.

HashMap<String,Integer> and getOrDefault count words. An ArrayList of keys is sorted with a comparator:

rankedWords.sort((a, b) -> {
    int byFrequency = Integer.compare(frequency.get(b), frequency.get(a));
    if (byFrequency != 0) {
        return byFrequency;
    }
    return a.compareTo(b);
});

Integer.compare avoids subtraction overflow. Reversing the count arguments puts larger counts first; String.compareTo handles ties.

collections.Counter performs the count. sorted(frequency, key=lambda word: (-frequency[word], word)) expresses descending count and ascending word order as one tuple key.

HashMap<&str,usize> counts borrowed words. sort_by compares counts in reverse order and chains the lexical comparison with then_with.

10.5 Approach and invariant

First count every occurrence. Then sort only the distinct words by the exact order the output requires. Copy the first k sorted words into the answer.

For i, love, leetcode, i, love, coding, the map contains:

word count
i 2
love 2
leetcode 1
coding 1

Sorting by frequency descending and then word ascending produces:

[i, love, coding, leetcode]

The first two words are the answer for k = 2.

Invariant: after counting any prefix of the input, the map contains the exact frequency of every word in that prefix. After sorting, every word appears before all words that rank below it under the problem’s two comparison rules.

10.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class TopKFrequentWordsSolution {
    static List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> frequency = new HashMap<>();
        for (String word : words) {
            frequency.put(word, frequency.getOrDefault(word, 0) + 1);
        }

        List<String> rankedWords = new ArrayList<>(frequency.keySet());
        rankedWords.sort((a, b) -> {
            int byFrequency = Integer.compare(frequency.get(b), frequency.get(a));
            if (byFrequency != 0) {
                return byFrequency;
            }
            return a.compareTo(b);
        });

        List<String> answer = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            answer.add(rankedWords.get(i));
        }
        return answer;
    }

    @Test public void ranksByFrequency() {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        assertEquals(List.of("i", "love"), topKFrequent(words, 2));
    }

    @Test public void returnsMostFrequentWordForKOne() {
        assertEquals(List.of("a"),
                     topKFrequent(new String[] {"b", "a", "a"}, 1));
    }

    @Test public void breaksTiesLexicographically() {
        String[] words = {"the", "day", "is", "sunny", "the", "the", "the",
                          "sunny", "is", "is"};
        assertEquals(List.of("the", "is", "sunny", "day"),
                     topKFrequent(words, 4));
    }

    @Test public void ordersWordsWhenAllFrequenciesTie() {
        assertEquals(List.of("a", "b", "c"),
                     topKFrequent(new String[] {"c", "a", "b"}, 3));
    }

    @Test public void returnsOneDistinctRepeatedWord() {
        assertEquals(List.of("echo"),
                     topKFrequent(new String[] {"echo", "echo", "echo"}, 1));
    }

    @Test public void returnsAllDistinctWordsInRankedOrder() {
        assertEquals(List.of("a", "b", "c"),
                     topKFrequent(new String[] {"c", "b", "a", "a", "b"}, 3));
    }

    @Test public void treatsEmptyStringAsOrdinaryWord() {
        assertEquals(List.of("", "a"),
                     topKFrequent(new String[] {"a", "", ""}, 2));
    }

    @Test public void comparesWordsCaseSensitively() {
        assertEquals(List.of("A", "a"),
                     topKFrequent(new String[] {"a", "A"}, 2));
    }

    public static void main(String[] args) {
        JUnitCore.main("TopKFrequentWordsSolution");
    }
}
import unittest
from collections import Counter


def top_k_frequent(words, k):
    frequency = Counter(words)
    ranked_words = sorted(frequency, key=lambda word: (-frequency[word], word))
    return ranked_words[:k]


class TopKFrequentWordsTests(unittest.TestCase):
    def test_ranks_by_frequency(self):
        words = ["i", "love", "leetcode", "i", "love", "coding"]
        self.assertEqual(["i", "love"], top_k_frequent(words, 2))

    def test_returns_most_frequent_for_k_one(self):
        self.assertEqual(["a"], top_k_frequent(["b", "a", "a"], 1))

    def test_breaks_ties_lexicographically(self):
        words = [
            "the",
            "day",
            "is",
            "sunny",
            "the",
            "the",
            "the",
            "sunny",
            "is",
            "is",
        ]
        self.assertEqual(["the", "is", "sunny", "day"], top_k_frequent(words, 4))

    def test_orders_words_when_all_frequencies_tie(self):
        self.assertEqual(["a", "b", "c"], top_k_frequent(["c", "a", "b"], 3))

    def test_treats_empty_string_as_ordinary_word(self):
        self.assertEqual(["", "a"], top_k_frequent(["a", "", ""], 2))

    def test_compares_words_case_sensitively(self):
        self.assertEqual(["A", "a"], top_k_frequent(["a", "A"], 2))


if __name__ == "__main__":
    unittest.main()
use std::collections::HashMap;

pub fn top_k_frequent<'a>(words: &[&'a str], k: usize) -> Vec<&'a str> {
    let mut frequency = HashMap::new();
    for &word in words {
        *frequency.entry(word).or_insert(0) += 1;
    }

    let mut ranked_words: Vec<&str> = frequency.keys().copied().collect();
    ranked_words.sort_by(|left, right| {
        frequency[right]
            .cmp(&frequency[left])
            .then_with(|| left.cmp(right))
    });
    ranked_words.truncate(k);
    ranked_words
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ranks_by_frequency() {
        let words = ["i", "love", "leetcode", "i", "love", "coding"];
        assert_eq!(vec!["i", "love"], top_k_frequent(&words, 2));
    }

    #[test]
    fn returns_most_frequent_for_k_one() {
        assert_eq!(vec!["a"], top_k_frequent(&["b", "a", "a"], 1));
    }

    #[test]
    fn breaks_ties_lexicographically() {
        let words = [
            "the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is",
        ];
        assert_eq!(vec!["the", "is", "sunny", "day"], top_k_frequent(&words, 4));
    }

    #[test]
    fn treats_empty_string_as_ordinary_word() {
        assert_eq!(vec!["", "a"], top_k_frequent(&["a", "", ""], 2));
    }

    #[test]
    fn compares_words_case_sensitively() {
        assert_eq!(vec!["A", "a"], top_k_frequent(&["a", "A"], 2));
    }
}

Each version returns an independent result collection containing exactly the first k ranked words.

10.7 High-value tests

Case Expected property
ordinary frequencies most common words first
all frequencies tied lexical ascending order
k = 1 one best word
k = unique count all words in ranked order
repeated identical word one distinct result

10.8 Complexity and correctness

Let \(n\) be the input length and \(u\) the number of distinct words. Counting costs \(O(n)\) expected time. Sorting the distinct words costs \(O(u\log u)\), and copying the answer costs \(O(k)\). Total time is \(O(n + u\log u)\) and space is \(O(u)\).

The count map gives every distinct word its exact frequency. The comparator implements the two required ranking rules in order, so the sorted list is exactly the required result order. Taking its first k elements therefore returns precisely the top k words.

10.9 If the interviewer pushes

  • If the interviewer requires \(O(u\log k)\) selection when \(k\) is much smaller than \(u\), keep a size-k priority queue after counting. Its comparator must place the worst retained word at the root.
  • If repeated top-k queries use the same counts, sort once and reuse the ranked list.
  • Define normalization explicitly before changing case or Unicode behavior.

10.10 TDD interview script

Confirm that output words are distinct, ranking is frequency descending then native lexical ascending, matching is case-sensitive, empty strings are ordinary words, and 1 <= k <= the distinct count. Then write this test list:

  1. One repeated word
  2. k = 1
  3. Ordinary frequencies
  4. Frequency tie
  5. All frequencies tied
  6. All distinct results
  7. Empty word
  8. Case sensitivity

For each red–green–refactor cycle, add one behavior, see the intended failure, make the smallest general change, and rerun the complete example. The returned order is part of the contract, so direct sequence equality is appropriate here. Do not assert map contents or comparator calls.

From book/src, run:

./java/run.sh TopKFrequentWordsSolution
./python/run.sh top_k_frequent_words_solution
./rust/run.sh top_k_frequent_words_solution

Describe the work as two independently testable phases: count every occurrence, then rank only distinct words. When the tie test arrives, extend the comparator with its secondary lexical rule rather than preprocessing the words.

10.10.1 Pseudocode

frequency = empty map
for each word:
    frequency[word]++

rankedWords = list of distinct map keys
sort rankedWords by:
    higher frequency first
    then lexicographically smaller word first

answer = first k ranked words copied into a new list
return answer

The counting invariant is that the map exactly represents the processed prefix. After sorting, each word precedes every word ranked below it by the two contract rules.

10.10.2 TDD sequence

Step Test code added Production code added or changed
1. One distinct word returnsOneDistinctRepeatedWord Count occurrences by word and create one ranked entry per distinct key, not per input occurrence.
2. Smallest k returnsMostFrequentWordForKOne Sort distinct keys by decreasing count and copy only the first result.
3. Ordinary ranking ranksByFrequency Accumulate several counts and return the first k distinct words in frequency order.
4. Secondary ordering lexical tie Add the language’s ordinary string comparison when frequency comparison is equal.
5. Every frequency tied ordersWordsWhenAllFrequenciesTie Triangulate that the secondary comparator is transitive across the full list.
6. Maximum k returnsAllDistinctWordsInRankedOrder Copy exactly k elements when k equals the distinct count; avoid returning a backing subList view.
7. Empty word treatsEmptyStringAsOrdinaryWord Confirm the empty string is counted and ranked with the same map and comparator logic.
8. Case contract case-sensitive words Preserve case-sensitive native string ordering without normalization.

The sequence isolates primary and secondary ranking rules. Boundary tests for both ends of k verify selection without adding behavior for invalid k, which the contract excludes.