---
title: Top K Frequent Words
difficulty: Medium
category: Hash Table / Heap (Sorting)
leetcode_id: 692
revision_count: 1
last_revision: 2026-09-12
---

# Top K Frequent Words

> **LeetCode:** [#692](https://leetcode.com/problems/top-k-frequent-words/)
> **Сложность:** Medium
> **Категория:** Hash Table / Heap (Sorting)

## Условие

Дан массив строк `words` и целое число `k`. Нужно вернуть `k` самых часто встречающихся строк. При равенстве частот строки сортируются в лексикографическом (алфавитном) порядке.

```
Input: words = ["i","love","leetcode","i","love","coding"], k = 2
  →  Output: ["i","love"]

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
  →  Output: ["the","is","sunny","day"]
```

## Ключевая идея

Сначала считаем частоты через hash map. Затем сортируем пары (слово, частота) — сначала по убыванию частоты, при равенстве — по возрастанию слова (лексикографически). Берём первые k.

## Оценка сложности

- **Сортировка:** O(n log n) время, O(n) память — n = `words.length`
- **Min-heap (Top-K):** O(n log k) время, O(n + k) память — быстрее при k << n, но в Ruby требует ручной реализации кучи

## Решение (Ruby)

```ruby
# @param {String[]} words
# @param {Integer} k
# @return {String[]}
def top_k_frequent(words, k)
  freq = Hash.new(0)
  words.each { |w| freq[w] += 1 }

  freq.sort_by { |word, count| [-count, word] }
      .first(k)
      .map(&:first)
end
```

## Разбор на примере

```
Input: words = ["i","love","leetcode","i","love","coding"], k = 2

Step 1: подсчёт частот
  "i" → 2, "love" → 2, "leetcode" → 1, "coding" → 1

Step 2: сортировка по [-count, word]
  [2, "i"], [2, "love"], [1, "coding"], [1, "leetcode"]

Step 3: первые k = 2 → ["i", "love"]

Result: ["i", "love"]
```

## Edge Cases

- `words` пустой → пустой массив (k = 0 на практике не бывает, но вернём [])
- `k = 1` → одно самое частое слово, при равенстве — лексикографически первое
- Все слова одинаковые → возвращаем k копий (или одно, если k=1)
- Все частоты одинаковы → чисто лексикографическая сортировка, берём первые k
- `words` содержит пустые строки — обрабатываются как обычные строки

## Типичные ошибки

- Неправильная сортировка при равенстве частот: забывают второй ключ `word` (лексикографический порядок возрастания)
- Неправильное направление: сортировка по возрастанию частоты вместо убывания
- `Hash#sort_by` возвращает массив пар, нужно извлечь только слова через `.map(&:first)`
- Не учитывают, что слово может быть пустой строкой

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Tally + sort | O(n log n) | O(n) | простота, годится для интервью |
| **Min-heap размера k** | **O(n log k)** | **O(n + k)** | **лучше при больших n и малых k** |
| Bucket sort | O(n) | O(n) | только если частоты не превышают n; нужна сортировка внутри bucket'а |

### Min-heap подход

```ruby
# @param {String[]} words
# @param {Integer} k
# @return {String[]}
def top_k_frequent(words, k)
  freq = Hash.new(0)
  words.each { |w| freq[w] += 1 }

  heap = []
  freq.each do |word, count|
    heap << [count, word]
    heap.sort_by! { |c, w| [-c, w] }  # имитация min-heap (упрощённо)
    heap.pop if heap.size > k
  end

  heap.sort_by { |c, w| [-c, w] }.map(&:last)
end
```

> **Важно:** В Ruby нет стандартной min-heap с кастомным компаратором. На интервью можно использовать `SortedSet` (gem) или встроенную сортировку для small k. Оптимальный вариант — сказать, что в production взяли бы `Containers::Heap` из `algorithms` gem или реализовали бинарную кучу руками.

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._