Problem statement

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

Solution

One solution is to use counter, put all words with their frequencies into heap and then extract top k: time complexity is O(n + k log n), space complexity is O(n). If we keep size of our heap not more than k, then complexity will be O(n log k), which is in fact worse than previous complexity. Note also, that here we did not take into account comparison of words if we have the same frequency, so complexity is more like O(n log k s), where s is average length of word.

Complexity

Time complexity is O(n*s*log k), space is O(n*s).

Code

class Solution:
    def topKFrequent(self, words, k):
        cnt, res = Counter(words), []
        heap = [(-freq, word) for word, freq in cnt.items()]
        heapq.heapify(heap)
            
        for _ in range(k):
            _, word = heappop(heap)
            res += [word]
            
        return res

Remark

There is also solution, using buckets, similar to problem 0347 Top K Frequent Elements, with complexity O(n + L) = O(ns), where L is total sum of length of words: the difficulty is what to do if we have words in the same bucket. We can use tries to sort words quickly (this is basically radix sort).