Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

692. Top K Frequent Words

Time: $O(n)$

Space: $O(n)$

			


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) {
      sort(begin(bucket[freq]), end(bucket[freq]));
      for (const string& word : bucket[freq]) {
        ans.push_back(word);
        if (ans.size() == k)
          return ans;
      }
    }

    throw;
  }
};




			


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.put(word, count.getOrDefault(word, 0) + 1);

    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();
  }
}




			


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

    for word, freq in 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