import collections
import Queue
class Solution(object):
def topKFrequent(self, words, k):
counter = collections.Counter(words)
frequency = collections.defaultdict(Queue.PriorityQueue)
limit = len(words)
res = []
for key, val in counter.items():
frequency[val].put(key)
while k > 0:
if frequency[limit]:
while k > 0 and not frequency[limit].empty():
res.append(frequency[limit].get())
k = 1
limit = 1
return res
Python bucket sort


Not sure you intended to put up a O(nlogn) algorithm but this algorithm is one. If we have O(n) elements of the same frequency, each of those buckets would have O(n) elements and there for populating the heap in those buckets would take O(nlogn) time. I just wanted to point this out because if we're resorting to an O(nlogn) algorithm we can solve it with no extra space as we can do heap sort, which is an inplace sorting algorithm, then return the last k elements.