LeetCode 692: Top K Frequent Words Solution

Master LeetCode problem 692 (Top K Frequent Words), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

692. Top K Frequent Words

Medium

Array Hash Table String Trie Sorting Heap (Priority Queue)Bucket Sort Counting

Problem Explanation

Explanation

To solve this problem, we can use a hashmap to store the frequency of each word in the input array. Then, we can use a priority queue (min heap) to keep track of the k most frequent words based on their frequency and lexicographical order. We will iterate through the hashmap and maintain the k most frequent words in the priority queue. If the size of the priority queue exceeds k, we will remove the least frequent word. Finally, we will extract the words from the priority queue in reverse order to get the k most frequent words sorted by frequency and lexicographical order.

Algorithm:

Create a hashmap to store the frequency of each word.
Iterate through the input array and update the frequency in the hashmap.
Create a priority queue (min heap) based on the custom comparator to compare words by frequency and lexicographical order.
Iterate through the hashmap and add words to the priority queue.
If the size of the priority queue exceeds k, remove the least frequent word.
Extract the words from the priority queue in reverse order to get the k most frequent words.

Time Complexity:

The time complexity of this approach is O(n log(k)), where n is the number of words in the input array.

Space Complexity:

The space complexity of this approach is O(n) for the hashmap and priority queue.

Solution Code

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freqMap = new HashMap<>();
        for (String word : words) {
            freqMap.put(word, freqMap.getOrDefault(word, 0) + 1);
        }
        
        PriorityQueue<String> pq = new PriorityQueue<>(
            (a, b) -> freqMap.get(a).equals(freqMap.get(b)) ? b.compareTo(a) : freqMap.get(a) - freqMap.get(b)
        );
        
        for (String word : freqMap.keySet()) {
            pq.offer(word);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        List<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(0, pq.poll());
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 692 (Top K Frequent Words)?

This page provides optimized solutions for LeetCode problem 692 (Top K Frequent Words) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 692 (Top K Frequent Words)?

The time complexity for LeetCode 692 (Top K Frequent Words) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 692 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 692 in Java, C++, or Python.

Back to LeetCode Solutions