692. Top K Frequent Words

Top K Frequent Words - LeetCode

Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1: Input: words = [“i”,“love”,“leetcode”,“i”,“love”,“coding”], k = 2 Output: [“i”,“love”] Explanation: “i” and “love” are the two most frequent words. Note that “i” comes before “love” due to a lower alphabetical order. Example 2: Input: words = [“the”,“day”,“is”,“sunny”,“the”,“the”,“the”,“sunny”,“is”,“is”], k = 4 Output: [“the”,“is”,“sunny”,“day”] Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] consists of lowercase English letters.
k is in the range [1, The number of unique words[i]]

  • code
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> freq = new HashMap<>();
        for (String word: words){
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
        
        // min heap, pop out the least frequency or the bigger lexi word
        PriorityQueue<String> q = new PriorityQueue<>( (a, b) ->
            freq.get(a) == freq.get(b) ? b.compareTo(a) : freq.get(a) - freq.get(b)
        );
        
        for (String word: freq.keySet()){
            q.offer(word);
            if (q.size() > k){
                q.poll();
            }
        }
        
        String[] res = new String[k];
        for (int i = k-1; i >= 0; --i){
            res[i] = q.poll();
        }
        return Arrays.asList(res);
    }
}