Top K Frequent Words

You are given a list of lowercase words words and an integer k. Return the k words that occur most often, as a list without repeats.

The result must be ordered from the most frequent word to the least frequent. When two words occur the same number of times, the one that comes first in alphabetical (lexicographic) order goes first; for example "ant" comes before "ants", which comes before "bee". This tie-breaking rule also decides which words make the cut when several share the k-th highest count.

Example 1

Example 2

Example 3

Constraints

• 1 <= words.length <= 104
• 1 <= words[i].length <= 10, lowercase English letters only
• 1 <= k <= number of distinct words

Pattern Path · Heaps & Top-K · problem 104 of 169

Start simple

For each of the k answer slots, scan every distinct word and recount its occurrences to pick the best remaining one: O(k·u·n) time for u distinct words.

The key idea

Two steps: count, then rank.

A hash map from word to count, built in one pass over the input, gives every frequency in O(n) time. The ranking rule is a composite key: higher count first, and among equal counts, the alphabetically smaller word first. Encoding it as the tuple (-count, word) lets an ordinary ascending sort do both at once, because tuples compare their first field and fall back to the second on ties. Take the first k words of the sorted list.

Sorting the u distinct words costs O(u log u). If u is large and k small, keep a heap of only k candidates instead, ordered so that the worst candidate (lowest count, then alphabetically last) sits on top and is evicted first. That brings ranking down to O(u log k), and you sort the k survivors at the end. Getting the tie-break direction right inside the heap is the subtle part, which is why the sort-based version is a good first answer.

Complexity

• Time: O(n + u log u)
• Space: O(u)

Python

from collections import Counter


class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        counts = Counter(words)
        # Most frequent first; equal counts fall back to alphabetical order.
        ranked = sorted(counts, key=lambda word: (-counts[word], word))
        return ranked[:k]

JavaScript

var topKFrequent = function(words, k) {
  const counts = new Map();
  for (const word of words) counts.set(word, (counts.get(word) || 0) + 1);

  // Most frequent first; equal counts fall back to alphabetical order.
  const ranked = [...counts.keys()].sort((a, b) => {
    const diff = counts.get(b) - counts.get(a);
    if (diff !== 0) return diff;
    return a < b ? -1 : a > b ? 1 : 0;
  });
  return ranked.slice(0, k);
};

What the interviewer is checking

The interviewer is testing hash-map counting plus a custom ordering, and whether you can upgrade to a size-k heap and get the inverted tie-break right inside it.

Mistakes to avoid

• Breaking ties in the wrong direction (reverse alphabetical), especially inside a min-heap.
• Returning the k words in heap order instead of sorted order.
• Comparing strings with a locale-aware function, which may not match plain character order.

Follow-ups to expect

• Achieve O(n log k). (Size-k heap with inverted tie-break.)
• Words arrive as an endless stream. (Count-min sketch plus heap.)
• Linear time when counts are bounded. (Bucket sort by frequency.)

In real software

Search engines and analytics dashboards report trending queries or top error messages this way, and autocomplete ranks suggestions by frequency with alphabetical tie-breaking.

Practice next