Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
    Note that "i" comes before "love" due to a lower alphabetical order.



Example 2:

Input: ["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.



Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.



Follow up:

Try to solve it in O(n log k) time and O(n) extra space.

Difficulty: interview

Starter code:

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        

Solutions:
class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         from collections import Counter
         count = Counter(words)
         common = sorted(list(count.items()), key=lambda item: (-item[1], item[0]))[:k]
         return [w for w, n in common]


class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         d = {}
         for word in words:
             d[word] = d.get(word, 0) + 1
         
         ret = sorted(d, key=lambda word: (-d[word], word))
         
         return ret[:k]


class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         from collections import Counter
         return [item[0] for item in sorted(Counter(words).items(),key = lambda x: (-x[1],x[0])) [:k]] 

class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         cnt = collections.Counter(words)
         word_freq = list(cnt.items())
         word_freq.sort(key=lambda item: (-item[1],item[0]))
         return [k for k, v in word_freq[:k]]

class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         cnt = {i:words.count(i) for i in list(set(words))}   
         cntRev = {}
         ans = []
         for key, val in cnt.items():
             if val not in cntRev:
                 cntRev[val]=[key]
             else:
                 cntRev[val].append(key)
         for num in sorted(cntRev,reverse=True):
             if k <= len(cntRev[num]):
                 ans+=sorted(cntRev[num])[:k]
                 break
             else:
                 ans+=sorted(cntRev[num])
                 k -= len(cntRev[num])
         return ans

class Solution:
     def topKFrequent(self, words, k):
         times_dict = {}
         for i in words:
             if i not in times_dict.keys():
                 times_dict[i] = 1
             else:
                 times_dict[i] += 1
         return_list = []
         for i in range(k):
             max = 0
             max_key = ""
             for j in times_dict.keys():
                 if times_dict[j] > max:
                     max = times_dict[j]
                     max_key = j
                 elif times_dict[j] == max and j < max_key:
                     max = times_dict[j]
                     max_key = j 
             del times_dict[max_key]
             return_list.append(max_key)
         return return_list

import heapq
 import functools
 
 
 @functools.total_ordering
 class Element:
     def __init__(self, word, count):
         self.word = word
         self.count = count
     
     def __eq__(self, other):
         return self.count == other.count and self.word == other.word
 
     def __gt__(self, other):
         if self.count == other.count:
             return self.word < other.word
         return self.count > other.count
 
 
 class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         heap = []
         for word, count in collections.Counter(words).items():
             heapq.heappush(heap, Element(word, count))
             if len(heap) > k:
                 heapq.heappop(heap)
         return [i.word for i in sorted(heap, reverse=True)]


import functools
 import collections
 
 class Solution(object):
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         wordCounts = collections.Counter(words)
         candidates = list(wordCounts.keys())
         candidates.sort(key = lambda word: (-wordCounts[word], word))
         return candidates[:k]
           

class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         counter = collections.Counter(words)
         keys = list(counter.keys())
         # Notice how this answer used a tuple in sorting so that it sorts based
         # on counter value first and then string alphabetical value the second
         keys.sort(key=lambda x: (-counter[x], x))
         return keys[:k]
         


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]]

class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         from collections import Counter
         c = Counter(words)
         buckets = [[] for _ in range(len(words)+1)]
         for key in c:
             buckets[c[key]].append(key)
         for b in buckets:
             b.sort()
         ans = []
         i = len(buckets) - 1
         while i >= 0:
             if len(ans) + len(buckets[i]) < k:
                 ans += buckets[i]
             else:
                 ans += buckets[i][:k - len(ans)]
                 break
             i -= 1
         return ans
 
 
 def __starting_point():
     s = Solution()
     print(s.topKFrequent(["i", "love", "leetcode", "i", "love", "coding"], 2))
__starting_point()

class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         c = collections.Counter(words).most_common()
         
         res = []
         
         while len(res) < k:
             temp = []
             node = c.pop(0)
             temp.append(node[0])
             while c and c[0][1] == node[1]:
                 node = c.pop(0)
                 temp.append(node[0])
             
             res.extend(sorted(temp))
             # print(res)
         
         return res[:k]

import heapq
 import functools
 @functools.total_ordering
 class Word:
     def __init__(self, str, c):
         self.s = str
         self.c = c
     def __eq__(self, other):
         return self.c == other.c and self.s == other.c
     def __le__(self, other):
         return self.c < other.c or (self.c == other.c and self.s > other.s)
     def __repr__(self):
         return self.s + str(self.c)
 class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         h = []
         d = {}
         for w in words:
             c = d.get(w, 0)
             c += 1
             d[w] = c
         for w in d.keys():
             heapq.heappush(h, Word(w, d[w]))
             if len(h) > k:
                 heapq.heappop(h)
         res = []
         while len(h) > 0:
             res.append(heapq.heappop(h))
         #print(res)
         return [w.s for w in reversed(res)]

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)   
         
         heap = []
         for word, count in counts.items():
             heapq.heappush(heap, Element(count, word))
             if len(heap) > k:
                 heapq.heappop(heap)
         
         res = []
         for _ in range(k):
             res.append(heapq.heappop(heap).word)
         return res[::-1]
     

class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         wDict=collections.Counter(words)
         res=[]
         maxHeap=[]
         for key,cnt in list(wDict.items()):
             heapq.heappush(maxHeap,(-cnt,key))
         for i in range(k):
             freq,word=heapq.heappop(maxHeap)
             res.append(word)
         return res


import collections
 import heapq
 
 
 def lexical_reverse(w):
     padding = [999] * (20 - len(w))
     return (w[0], [200 - ord(x) for x in w[1]] + padding)
 
 
 class Solution:
     def topKFrequent(self, words, k):
         """
         :type words: List[str]
         :type k: int
         :rtype: List[str]
         """
         freq = collections.defaultdict(int)
         for w in words:
             freq[w] += 1
         word_pairs = []
         for w in freq.keys():
             word_pairs.append((freq[w], w))
 
         heapq.heapify(word_pairs)
         return [w[1] for w in heapq.nlargest(
             k, word_pairs, lexical_reverse)]