692. Top K Frequent Words

/**

* 692. Top K Frequent Words

* Given a non-empty list of words, return the k most frequent elements.

* Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency,

* then the word with the lower alphabetical order comes first.

* Example 1:

* Input: [“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.

*/

This is a common interview question with an interesting twist on priority queue. See my solution here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/TopKFrequentWords.java

The approach uses:

  1. Use a hash map to aggregate the count
  2. Use priority queue to prioritizing words by lower frequency and higher alphabetical order on top (this is opposite of what the question asked but is being done so we can trim words at top of the priority queue).
  3. Add items from map to priority queue while trimming its size when it becomes greater than K.
  4. Copy the PQ to a list.
  5. Reverse the order of words in list so that they are highest to lowest by frequency and lower alphabetical order with same frequency has precedence.

Here is the code:

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> wordCount = new HashMap<>();
    //use map to count the data
    for (String word : words) {
        Integer i = wordCount.getOrDefault(word, 0);
        wordCount.put(word, i+ 1);
    }
    PriorityQueue<WordCount> priorityQueue = new PriorityQueue<WordCount>(
            (l, m)-> {
                if (l.count.equals(m.count)) {
                    //keep larger words with same occurrence at top (see how order of l & m is switched below)
                    return m.word.compareTo(l.word);
                } else {
                    //keep smaller occurrences at top of PQ
                    return Integer.<em>compare</em>(l.count , m.count);
                }
            } );
    for (Map.Entry<String, Integer> mapVal : wordCount.entrySet()) {
        priorityQueue.offer(new WordCount(mapVal.getKey(), mapVal.getValue()));
        if (priorityQueue.size() > k) {
            priorityQueue.poll();   //trim pq size when its greater than threshold
        }
    }
    List<String> strings = new ArrayList<>();
    //important to use poll here to get next head from the pq. we cant just iterate over the pq
    while (!priorityQueue.isEmpty()) {
        strings.add(priorityQueue.poll().word);
    }
    //reverse the collection such that words with higher frequency and lower alphabetical count are at the beginning
    Collections.reverse(strings);
    return strings;
}