Top K Frequent Words - leetcode

topKFrequent1.py

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

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.

collections.Counter([iterable-or-mapping]) counts hashable objects
>>> myList = [1,1,2,3,4,5,3,2,3,4,2,1,2,3]
>>> print Counter(myList)
Counter({2: 4, 3: 4, 1: 3, 4: 2, 5: 1})

Both list.sort() and sorted() have a "key" parameter to specify a 
function to be called on each list element prior to making comparisons.

Complexity Analysis:

Time Complexity: O(NlogN), where N is the length of words. 
We count the frequency of each word in O(N) time, 
then we sort the given words in O(NlogN) time.

Space Complexity: O(N) the space used to store our candidates.

"""
from collections import Counter

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        
        # returns Counter object with counts
        count = collections.Counter(words)
        
        # turn dict_keys into list
        candidates = list(count.keys())
        
        # sort in place to save space
        # key = lambda w: (-count[w], w) 
        #    apply lambda function to each key
        #    -count[w] will sort by the frequency first, in descending order
        #    w will sort by alphabetical order in the case of a tie
        candidates.sort(key = lambda w: (-count[w], w))
        
        # get first k elements
        return candidates[:k]