Top K Frequent Words - Leetcode Solution

Problem Description:

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.

Solution:

We can solve this problem by using a hash map to count the frequency of each word. Then we can sort the hash map by frequency and alphabetical order to get the k most frequent words.

Algorithm:

1. Create a hash map freq to store the frequency of each word.
2. For each word in the input list, add it to the hash map and update its frequency.
3. Sort the hash map by frequency in descending order. If two words have the same frequency, sort them by alphabetical order.
4. Take the first k words from the sorted hash map and return them.

Code:

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        freq = {}
        for word in words:
            freq[word] = freq.get(word, 0) + 1
        
        sorted_freq = sorted(freq.items(), key=lambda x: (-x[1], x[0]))
        return [x[0] for x in sorted_freq][:k]

Time Complexity:

The time complexity of this solution is O(n log n) because of the sorting step. The space complexity is O(n) because of the hash map.

1