460. Top K Frequent Words
You are given a list of lowercase words words and an integer k. Return the k words that appear most often, as a list.
The list must be ordered from most frequent to least frequent, and whenever two words are tied on frequency, the one that comes earlier in dictionary (lexicographic) order goes first. That tie rule makes the answer unique.
Example 1:
Input: words = ["go", "java", "go", "python", "java", "go"], k = 2
Output: ["go", "java"]
Explanation: go appears 3 times and java twice, so they are the two most common. python (once) misses the cut.
Example 2:
Input: words = ["spark", "ember", "ash", "spark", "ember", "spark", "flame"], k = 3
Output: ["spark", "ember", "ash"]
Explanation: Counts: spark 3, ember 2, ash 1, flame 1. ash and flame tie at 1, and ash comes first alphabetically, so it takes the third slot.
Constraints:
- 1 ≤ words.length ≤ 500
- 1 ≤ words[i].length ≤ 10; words[i] consists of lowercase English letters
- 1 ≤ k ≤ number of distinct words
Hints:
Counting is the easy half — one hash-map pass. The real puzzle is the ordering rule: write a comparator that puts higher counts first and, on equal counts, the alphabetically smaller word first, then let it drive whatever structure you choose.
A full sort of the distinct words is O(n log n). To beat it, keep a min-heap capped at k entries ordered by the REVERSED comparator — weakest candidate on top — and evict the top whenever the heap grows past k. Popping the survivors yields the answer back-to-front.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["go", "java", "go", "python", "java", "go"], k = 2
Expected output: ["go", "java"]