692. Top K Frequent Words LeetCode Solution

In this guide, you will get 692. Top K Frequent Words LeetCode Solution with the best time and space complexity. The solution to Top K Frequent Words problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Top K Frequent Words solution in C++
Top K Frequent Words solution in Java
Top K Frequent Words solution in Python
Additional Resources

692. Top K Frequent Words LeetCode Solution image

Problem Statement of Top K Frequent Words

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.

Example 1:

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.

Example 2:

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[i]]

Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

692. Top K Frequent Words LeetCode Solution in C++

class Solution {
 public:
  vector<string> topKFrequent(vector<string>& words, int k) {
    const int n = words.size();
    vector<string> ans;
    vector<vector<string>> bucket(n + 1);
    unordered_map<string, int> count;

    for (const string& word : words)
      ++count[word];

    for (const auto& [word, freq] : count)
      bucket[freq].push_back(word);

    for (int freq = n; freq > 0; --freq) {
      ranges::sort(bucket[freq]);
      for (const string& word : bucket[freq]) {
        ans.push_back(word);
        if (ans.size() == k)
          return ans;
      }
    }

    throw;
  }
};
/* code provided by PROGIEZ */

692. Top K Frequent Words LeetCode Solution in Java

class Solution {
  public List<String> topKFrequent(String[] words, int k) {
    final int n = words.length;
    List<String> ans = new ArrayList<>();
    List<String>[] bucket = new List[n + 1];
    Map<String, Integer> count = new HashMap<>();

    for (final String word : words)
      count.merge(word, 1, Integer::sum);

    for (final String word : count.keySet()) {
      final int freq = count.get(word);
      if (bucket[freq] == null)
        bucket[freq] = new ArrayList<>();
      bucket[freq].add(word);
    }

    for (int freq = n; freq > 0; --freq)
      if (bucket[freq] != null) {
        Collections.sort(bucket[freq]);
        for (final String word : bucket[freq]) {
          ans.add(word);
          if (ans.size() == k)
            return ans;
        }
      }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

692. Top K Frequent Words LeetCode Solution in Python

class Solution:
  def topKFrequent(self, words: list[str], k: int) -> list[str]:
    ans = []
    bucket = [[] for _ in range(len(words) + 1)]

    for word, freq in collections.Counter(words).items():
      bucket[freq].append(word)

    for b in reversed(bucket):
      for word in sorted(b):
        ans.append(word)
        if len(ans) == k:
          return ans
 # code by PROGIEZ