Top K Frequent Words

Problem Statement: 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 = ["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]]

Source: https://leetcode.com/problems/top-k-frequent-words/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

    def topKfrequent(self, words, k):
        """
        words: List[str]
        k: int
        return: List[str]
        """
        counter={}
        for i in words:
            if i in counter:
                counter[i]+=1
            else:
                counter[i]=1
    
        heap=[]
        for key,value in counter.items():
            heapq.heappush(heap, (-1*value, key))
    
        return [heapq.heappop(heap)[1] for word in range(k)]

Thought Process / Explanation:

Heapq uses a priority queue to implement heaps. So by default, we will get lexicographically sorted strings. Now the task is to main freq and word pair in a heap where the top is max-freq.

Thank You!