692. Top K Frequent Words

Problem Description

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Examples:

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

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

Constraints:

• 1 ≤ words.length ≤ 500
• 1 ≤ words[i].length ≤ 10
• words[i] consists of lowercase English letters
• k is in the range [1, The number of unique words]

Python Solution

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        # Count word frequencies
        word_count = Counter(words)
        
        # Create a heap of (-frequency, word) pairs
        # Using negative frequency to create a max heap
        heap = [(-freq, word) for word, freq in word_count.items()]
        heapify(heap)
        
        # Get top k elements
        result = []
        for _ in range(k):
            freq, word = heappop(heap)
            result.append(word)
            
        return result

Implementation Notes:

• Uses Counter to count word frequencies
• Creates a min heap with (-frequency, word) pairs
• Negative frequency creates max heap behavior
• Time complexity: O(n log k) where n is the length of words
• Space complexity: O(n) for the counter and heap

Java Solution

class Solution {
    public List topKFrequent(String[] words, int k) {
        // Count word frequencies
        Map wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        
        // Create priority queue with custom comparator
        PriorityQueue> pq = new PriorityQueue<>(
            (a, b) -> a.getValue().equals(b.getValue()) ?
                b.getKey().compareTo(a.getKey()) :
                a.getValue() - b.getValue()
        );
        
        // Add entries to priority queue, maintaining size k
        for (Map.Entry entry : wordCount.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        // Build result list
        List result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(0, pq.poll().getKey());
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector topKFrequent(vector& words, int k) {
        // Count word frequencies
        unordered_map wordCount;
        for (const string& word : words) {
            wordCount[word]++;
        }
        
        // Custom comparator for priority queue
        auto comp = [](pair& a, pair& b) {
            return a.second > b.second || 
                   (a.second == b.second && a.first < b.first);
        };
        
        // Create min heap
        priority_queue, 
                      vector>, 
                      decltype(comp)> pq(comp);
        
        // Add entries to priority queue
        for (const auto& entry : wordCount) {
            pq.push(entry);
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
        // Build result vector
        vector result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pq.top().first;
            pq.pop();
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) {
    // Count word frequencies
    const wordCount = new Map();
    for (const word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }
    
    // Convert to array and sort
    return Array.from(wordCount.entries())
        .sort((a, b) => 
            b[1] === a[1] ? 
            a[0].localeCompare(b[0]) : 
            b[1] - a[1]
        )
        .slice(0, k)
        .map(entry => entry[0]);
};

C# Solution

public class Solution {
    public IList TopKFrequent(string[] words, int k) {
        // Count word frequencies
        Dictionary wordCount = new Dictionary();
        foreach (string word in words) {
            if (!wordCount.ContainsKey(word)) {
                wordCount[word] = 0;
            }
            wordCount[word]++;
        }
        
        // Create priority queue with custom comparison
        var pq = new SortedDictionary<(int freq, string word), string>(
            Comparer<(int freq, string word)>.Create((a, b) => {
                if (a.freq != b.freq) {
                    return a.freq.CompareTo(b.freq);
                }
                return b.word.CompareTo(a.word);
            })
        );
        
        // Add entries to priority queue
        foreach (var entry in wordCount) {
            pq.Add((-entry.Value, entry.Key), entry.Key);
            if (pq.Count > k) {
                pq.Remove(pq.Last().Key);
            }
        }
        
        // Return top k words
        return pq.Values.Take(k).ToList();
    }
}

Implementation Notes:

• Uses dictionary/map to count word frequencies
• Different approaches for different languages based on available data structures
• Python and JavaScript solutions are more concise due to built-in sorting capabilities
• Java and C++ use priority queues for efficient k-element selection
• C# uses SortedDictionary as an alternative to priority queue
• Time complexity: O(n log k) for heap-based solutions, O(n log n) for sorting-based solutions
• Space complexity: O(n) for storing word frequencies