Rank the K Most Repeated Words in a Document

Medium20–25 min

Topics

HeapHash MapSortingString

Companies

AmazonGoogleMicrosoft

Given the words of a document, return the k words that appear most often, ranked from most to least frequent. When two words appear the same number of times, the alphabetically earlier word ranks higher.

Sorting every distinct word gives the answer but orders words that can never make the cut. A size-k heap that keeps the worst-ranked candidate at its root lets each word be judged with a single O(log k) push and, when the heap overflows, a single eviction.

Test Case 1:

Input:words = ["pear","fig","pear","kiwi","fig","pear","kiwi","date"], k = 2

Output:["pear", "fig"]

Explanation:pear appears 3 times. fig and kiwi tie on 2 appearances, and fig comes first alphabetically.

Test Case 2:

Input:words = ["b","a","b","a"], k = 1

Output:["a"]

Explanation:a and b tie on 2 appearances; a is alphabetically first, so it is the only one returned.

Test Case 3:

Input:words = ["ab","abc","ab","abc","a"], k = 3

Output:["ab", "abc", "a"]

Explanation:"ab" and "abc" tie on 2; the shorter "ab" sorts before "abc". "a" appears once and ranks last.

Constraints

◆1 ≤ words.length ≤ 100
◆Each word is 1 to 10 lowercase English letters
◆1 ≤ k ≤ the number of distinct words in the document
◆Rank by how many times a word appears (highest first); words that appear equally often are ranked alphabetically (a before b)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Count, Then Fully Sort Every Distinct Word

Brute

Count each word's appearances in a map, then sort every distinct word by the ranking rule (more appearances first, alphabetical among ties) and take the first k. It is correct and short, but it fully orders all m distinct words even though only the top k positions are ever used.

TimeO(m log m)

SpaceO(m)

Java

Try it out

class Solution {
    public String[] topRepeatedWords(String[] words, int k) {
        Map<String, Integer> counts = new TreeMap<>();
        for (String word : words) counts.merge(word, 1, Integer::sum);
        List<String> ranked = new ArrayList<>(counts.keySet());
        ranked.sort((a, b) -> {
            if (!counts.get(a).equals(counts.get(b))) return counts.get(b) - counts.get(a);
            return a.compareTo(b);
        });
        String[] result = new String[k];
        for (int i = 0; i < k; i++) result[i] = ranked.get(i);
        return result;
    }
}

Optimal — Size-k Heap With the Worst-Ranked Word on Top

Optimal

After counting, walk the distinct words once while keeping a min-heap of at most k words ordered so that the WORST-ranked word sits at the root (fewest appearances; among ties, the alphabetically later word is worse). Push each word and, whenever the heap grows past k, evict the root — that word can never be in the top k. When the walk ends the heap holds exactly the k best words, and popping it yields them worst-first, so they are written into the result from the last position backward. Each heap operation costs O(log k) instead of the O(log m) a full sort would spend per comparison.

TimeO(n + m log k)