# Python 3 solution with O(nlogk) and O(n)

• ``````import collections
import heapq
import functools

@functools.total_ordering
class Element:
def __init__(self, count, word):
self.count = count
self.word = word

def __lt__(self, other):
if self.count == other.count:
return self.word > other.word
return self.count < other.count

def __eq__(self, other):
return self.count == other.count and self.word == other.word

class Solution(object):
def topKFrequent(self, words, k):
"""
:type words: List[str]
:type k: int
:rtype: List[str]
"""
counts = collections.Counter(words)

freqs = []
heapq.heapify(freqs)
for word, count in counts.items():
heapq.heappush(freqs, (Element(count, word), word))
if len(freqs) > k:
heapq.heappop(freqs)

res = []
for _ in range(k):
res.append(heapq.heappop(freqs)[1])
return res[::-1]

``````

• @nychent Where does this account for words withe the same frequency, in which you then order alphabetically (ascending)

• @emdu
I think this part handles that.

``````def __lt__(self, other):
if self.count == other.count:
return self.word > other.word
return self.count < other.count

def __eq__(self, other):
return self.count == other.count and self.word == other.word``````

• Here's a 95% speed solution.
(1) Use collections.Counter to collate
(2) create list of touples containing (word,count)
(3) Sort by the count and secondary by the word. Note that by negating the count we sort from highest count to lowest instead of the other way around. (Note also that you can't just do a reverse sort or the words themselves would be the wrong way around.)
(4) Strip off and return a list of the first K words.

``````class Solution:
def topKFrequent(self, words, k):
counts = collections.Counter(words)
items = list(counts.items())
items.sort(key=lambda item:(-item[1],item[0]))
return [item[0] for item in items[0:k]]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.