Top K Frequent Words-LeetCode-Amazon Interview Question

The problem description can be found here.

This problem does not have any hidden trick unlike some other problems where trick is buried in the depth of language. It is pretty straight forward in giving us hint that we have to use heap.

So, what makes it straight forward ? simplicity of language 🙂.

“Top K Frequent Word” ,when we see terms like top k, highest, maximum value or bottom k , lowest, minimum value, we know we have to use max Heap or min Heap respectively.Heap offers the constant time(O(1)) element retrieval. And, of course it will take O(logN) time to reorganize the tree if we delete the max/min element in order to access the next max/min element.Reorganizing the tree ensures that max/min element is always at the top of the tree i.e always available at constant time which is also the core requirement on which heap is built. Heap is implemented using priority queue. Unlike queue whose retrieval policy is first in first out, priority queue’s retrieval policy has to do with the priority associated with that element. The first element to be retrieved is the element that has highest/lowest or custom priority associated to it.

With above insight following are steps to solution:

1. Count the words by frequency , store the word as a key in hash table and frequency as the value for that key. Use map for storing key value pairs as it stores elements in non decreasing order. I chose map because the question mentions that: “If two words have the same frequency, then the word with the lower alphabetical order comes first.” If order was not important I could have used unordered map as it offers better time complexity.
2. Insert frequency of words in priority queue with the goal of accessing max element at constant time.
3. Iterate through map and pick a word from map for which its frequency matches to the current max value in heap and store that word in the result. Repeat this process for k times. During this process, you have to delete the word from map that gets stored in the result because we are picking the word based on frequency. We want to make sure that we are not picking the same word twice as more than 1 words might have same frequency. We want to pick different word each time we look at map. Deleting the word and it’s frequency from map ensures that the next highest frequent word can be the word that has same frequency as the deleted word. Without delete there is a risk that same word appears in the result if more than one word has same frequency.

vector<string> topKFrequent(vector<string>& words, int k) {
    
        vector<string> result; 
        
        map<string,int> ht_freq; 
        
        for(int i=0; i<words.size(); i++){
            if(ht_freq.find(words[i]) == ht_freq.end()){
                ht_freq[words[i]] = 1;
            }else{
                ht_freq[words[i]] = ht_freq[words[i]] +1; 
            }
        }
        
        priority_queue<int> freq_vec ;
        
        map<string,int>::iterator it ; 
        for(it = ht_freq.begin(); it != ht_freq.end() ;it++ ){
            freq_vec.push(it->second);
        }
        
        
        while(k>0){
            
        for(it = ht_freq.begin(); it != ht_freq.end() ;it++ ){
            if(freq_vec.top() == it->second){
                result.push_back(it->first);
                //delete that value in map because we might 
                //have more than one word with same frequency
                ht_freq.erase(it);
                break;
            }
            
        }
        
        freq_vec.pop(); 
            
        k--;
            
        } //end of while 
   
        return result; 
    } //end of the function

Do not forget to provide feedback :)