# Python with explanation

• We know that the maximum frequency of words cannot exceed N because there is only a maximum of N words.

Input: `["i", "love", "leetcode", "i", "love", "coding"]`

Frequency: `{"i": 2, "love": 2, "leetcode": 1, "coding": 1}`

Group by frequency: `{ 1: ["leetcode", "coding"], 2: ["i", "love"] }`

Hence we can count the frequency of the words and group them by frequency. Iterate through the group starting from a frequency of N and collect until you have at least k words. We then sort the final list and that takes approximately O(klgk), worst case O(nlgn) if every word only appears once.

``````class Solution(object):
def topKFrequent(self, words, k):
"""
:type words: List[str]
:type k: int
:rtype: List[str]
"""
# Time: O(n + klgk)
# Space: O(n)
from collections import Counter
counter = Counter(words)
freqs = {}
for word, count in counter.items():
if count not in freqs:
freqs[count] = []
freqs[count].append(word)
res = []
for i in range(len(words), 0, -1):
if i in freqs:
for word in freqs[i]:
res.append((word, i))
if len(res) >= k:
break
res.sort(cmp=lambda a, b: (b[1] - a[1]) if a[1] != b[1] else (-1 if a[0] < b[0] else 1))
return [el[0] for el in res[:k]]
``````

- Yangshun

• In worst case, where every word appears once, you will get `n` elements in `res` which costs you `O(nlgn)` to sort it.

• Thank you for sharing this solution. ^ ^

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