Top K Frequent Words LeetCode Solution

Problem Statement

Top K Frequent Words LeetCode Solution – 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

Test Case 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.

Approach:

this is the comparison struct for 2 conditions:

1- keep the descending order (highest frequency first in the priority queue)

2- if the two words have the same frequency, then compare the two strings:

This question can be solved by maintaining a HashMap to count the frequency of words and a priority queue (min-heap) to get the K Top Frequent Words.

Define a class to store the word and its frequency. Implement the compareTo method which is used by the minHeap to sort and store the object in the heap. The trick to solving this question lies in this compareTo method.

The question asks us to return the top words in lexicographically order if they have the same frequency. So, let’s store the words in the min-heap in such a way that the words with the same frequency are stored in reverse of lexicographical order, so that whenever we come across a word with the same frequency, we pop out the word that comes last in the order.

In the following implementation, I make use of Map.Entry class intensively. Hence keeping the <word, frequency> information together whenever I need them, improving the efficiency of the code.

Code for Top K Frequent Words

C++ Program

class compare{
    public:
        bool operator()(pair<int,string> pair1,pair<int,string> pair2){
          
            if(pair1.first != pair2.first)
                return pair1.first < pair2.first;
            else
                return pair1.second>=pair2.second;
        }
    
};

class Solution {
public:
       vector<string> topKFrequent(vector<string>& words, int k) {
       priority_queue<pair<int,string>,vector<pair<int,string>>,compare> pq;
       unordered_map<string,int> umap;
       
       for(string word:words)
           umap[word]++;
        
       for(auto itr=umap.begin();itr!=umap.end();itr++)
       {
           pq.push(make_pair(itr->second,itr->first));
       }
        
       vector<string> freqWords;
       
        while(k>0)
        {
            freqWords.push_back(pq.top().second);
            pq.pop();
            k--;
        }
        
        return freqWords;
    }
};

Java Program

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 0);
            }
            map.put(word, map.get(word) + 1);
        }
        
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
      @Override
      public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
        if (e1.getValue() != e2.getValue()) {
          return e1.getValue().compareTo(e2.getValue());
        } else {
          return e2.getKey().compareTo(e1.getKey());
        }
      }
        }); 
        
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while (!minHeap.isEmpty()) {
        	ret.add(minHeap.poll().getKey());
        }
        
        Collections.reverse(ret);
        return ret;
    }
}

Complexity Analysis for Top K Frequent Words LeetCode Solution

Time complexity: O(nlogK) where n is the length of the input words[] array.
This is due to the Heap being of size K, and we put in/out for a total of n times.

Space complexity: O(n) because of the map used.