Skip to main content

692. Top K Frequent Words

medium

Return the k most frequent words from a list, ties broken by lexicographic order. Tests heap usage with a custom comparator — a common trip-up under time pressure.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

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]].

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count frequencies first — a hash map gets you there in one pass.

Hint 2

Now you need 'top k' from the (word, count) pairs. Sound familiar? Heap.

Hint 3

The tricky part is the comparator: higher count first, but ties broken by lexicographically smaller word first. A min-heap of size k means you flip both signs of the comparator.

Hint 4

Push (count, word) pairs into a min-heap with custom ordering. If size > k, pop. At the end, pop everything and reverse for descending output.

Solution approach

Reveal approach

Two passes. First, count word frequencies in a hash map. Then push (count, word) pairs into a min-heap of size k with a custom comparator: prefer smaller count, and when counts tie, prefer lexicographically larger word (because this is a MIN-heap and we want to evict the 'worst' top-k candidate). If the heap exceeds size k, pop. After all words are processed, pop all k entries and reverse for descending-frequency output. O(n log k) time, O(n) space. Buckets-by-frequency + sort each bucket is another option (O(n + sum k_i log k_i)) but the heap version is cleaner to explain.

Complexity

Time
O(n log k)
Space
O(n)

Related patterns

  • heap
  • hash-map
  • top-k

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg
  • Uber
  • Meta

Practice these live with InterviewChamp.AI

Drill Top K Frequent Words and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →