DSA problem
Top K Frequent Words
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 — i.e. alphabetically ascending — so that ties break in a deterministic, dictionary-friendly way.
A direct approach counts the words with a hash map, then sorts the unique words by the comparator (-count, word). That works in O(n + k_unique log k_unique) time but uses a general-purpose comparison sort even though the frequencies themselves are bounded small integers.
The bucket sort approach turns that observation into a linear-ish algorithm. Because no word can appear more than n = words.length times, the possible frequencies live in [1, n]. Build buckets indexed by frequency, where buckets[i] is the list of all distinct words appearing exactly i times. Within each bucket, sort the words lexicographically so the tie-break rule is honored.
Finally, scan the buckets from index n down to 1 and append words until you have collected k of them. The dominant cost is the per-bucket lexicographic sort, which is bounded by O(k_unique log k_unique) in the worst case but is in practice cheap because each bucket is usually small. An equally famous alternative uses a heap of size k ordered by (-count, word), which is O(n log k) and works well when k is small.
Examples
words = ["i","love","leetcode","i","love","coding"], k = 2["i","love"]words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4["the","is","sunny","day"]words = ["a","aa","aaa"], k = 1["a"]Constraints
- 1 <= words.length <= 500
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters.
- k is in the range [1, the number of unique words].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.