Python with explanation

  • 3

    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] = []
            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:
            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

  • 0

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

  • 1

    Thank you for sharing this solution. ^ ^

Log in to reply

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