Given an array of strings words and an integer k, return the k most frequent strings. Sort ties by lexicographical order (the word that comes first alphabetically ranks higher).
Example 1
Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" both appear twice, tied — "i" and "love" are the two most frequent, order by frequency then alphabetically.
1 <= words.length <= 5001 <= k <= number of unique wordsFirst count frequencies with a hash map — this part is a straightforward application of the frequency-map pattern.
The tie-breaking rule (lexicographical order among equal frequencies) needs to be encoded directly into the heap's comparator, not handled as an afterthought.
A min-heap of size k, evicting the 'worst' candidate (lowest frequency, or lexicographically largest on a tie) as you go, avoids sorting every unique word.
public 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: lowest frequency first; on a tie, LEXICOGRAPHICALLY LARGER first (so it's evicted first, keeping the better tie)
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 word : freq.keySet()) {
heap.offer(word);
if (heap.size() > k) heap.poll(); // evict the current worst candidate
}
List<String> result = new ArrayList<>();
while (!heap.isEmpty()) result.add(heap.poll());
Collections.reverse(result); // heap pops worst-to-best; reverse for best-to-worst output order
return result;
}Time: O(n log k) · Space: O(n)