Skip to content

692. Top K Frequent Words 👍

Approach 1: Bucket Sort

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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

Approach 2: Follow up

  • Time: $O(n\log k)$
  • Space: $O(n\log k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct T {
  string word;
  int freq;
  T(string word, int freq) : word(word), freq(freq) {}
};

class Solution {
 public:
  vector<string> topKFrequent(vector<string>& words, int k) {
    vector<string> ans;
    unordered_map<string, int> count;
    // Words w/ higher frequency and lower alphabetical order are in the bottom
    // Of the heap, because we'll pop words w/ lower frequency and higher
    // Alphabetical order if the heap's size > k
    auto compare = [](const T& a, const T& b) {
      return a.freq == b.freq ? a.word < b.word : a.freq > b.freq;
    };
    priority_queue<T, vector<T>, decltype(compare)> heap(compare);

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

    for (const auto& [word, freq] : count) {
      heap.emplace(word, freq);
      if (heap.size() > k)
        heap.pop();
    }

    while (!heap.empty())
      ans.push_back(heap.top().word), heap.pop();

    reverse(begin(ans), end(ans));
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class T {
  public String word;
  public int freq;
  public T(String word, int freq) {
    this.word = word;
    this.freq = freq;
  }
};

class Solution {
  public List<String> topKFrequent(String[] words, int k) {
    List<String> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();
    // Words w/ higher frequency and lower alphabetical order are in the bottom
    // Of the heap, because we'll pop words w/ lower frequency and higher
    // Alphabetical order if the heap's size > k

    Queue<T> heap = new PriorityQueue<>(
        (a, b) -> a.freq == b.freq ? b.word.compareTo(a.word) : a.freq - b.freq);

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

    for (final String word : count.keySet()) {
      heap.offer(new T(word, count.get(word)));
      if (heap.size() > k)
        heap.poll();
    }

    while (!heap.isEmpty())
      ans.add(heap.poll().word);

    Collections.reverse(ans);
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class T:
  def __init__(self, word: str, freq: int):
    self.word = word
    self.freq = freq

  def __lt__(self, other):
    if self.freq == other.freq:
      # Words w/ higher frequency and lower alphabetical order are in the bottom
      # Of the heap, because we'll pop words w/ lower frequency and higher
      # Alphabetical order if the heap's size > k
      return self.word > other.word
    return self.freq < other.freq


class Solution:
  def topKFrequent(self, words: List[str], k: int) -> List[str]:
    ans = []
    heap = []  # Sorted by freq then alphabet

    for word, freq in collections.Counter(words).items():
      heapq.heappush(heap, T(word, freq))
      if len(heap) > k:
        heapq.heappop(heap)

    while heap:
      ans.append(heapq.heappop(heap).word)

    return ans[::-1]