MediumArrayHash TableStringTrieSortingHeapBucket SortCountingUpdated Sep 2026

692. Top K Frequent Words

Asked at Rippling

Difficulty

Medium

Time

O(n log k)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given a list of strings called words and an integer k. Return the k strings that appear most often in the list.

Order the answer by frequency, highest first. When two words have the same frequency, put the one that comes first in lexicographical order (dictionary order) earlier. So a word with a smaller letter-by-letter order wins a tie.

The output is a list of exactly k words. Each word appears in the output only once, even if it repeats many times in the input.

Count first, then order

wordsiloveleetcodeilovecoding012345"i" and "love" each appear twice — they are the top 2i → 2love → 2leetcode → 1coding → 1
We need the k words with the biggest counts, and ties are broken by dictionary order.

Constraints

  • ●1 <= words.length <= 500
  • ●1 <= words[i].length <= 10
  • ●words[i] consists of lowercase English letters
  • ●k is in the range [1, number of unique words]

Examples

Example 1
Inputwords = ["i","love","leetcode","i","love","coding"], k = 2
Output["i","love"]
Why"i" and "love" both appear 2 times, and no other word appears more. They tie on frequency, so we compare them as strings: "i" is smaller than "love", so "i" comes first.
Example 2
Inputwords = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output["the","is","sunny","day"]
WhyThe counts are the=4, is=3, sunny=2, day=1. No two words share a count here, so we simply list them from the largest count to the smallest.

Asked At

1 companies
CompanyDifficulty
RipplingMediumView all Rippling questions →

How to Think About It

1

Count word frequencies using a hash map

2

Use a min-heap of size k to keep track of top k frequent words

3

Compare words by frequency first, then lexicographically if tied

4

Extract elements from heap in reverse order for final result

5

Consider bucket sort as an alternative O(n) approach

Optimal Approach

Count word frequencies using a hash map. Use a min-heap of size k that compares words by frequency first, then lexicographically in reverse for proper ordering. Iterate through all words, adding each to the heap and removing the smallest when size exceeds k. Extract elements from the heap and reverse the result for correct order.

Min-heap of size k

heap (weakest on top)(2, love)(2, i)← topAfter all words: the heap holds the 2 best, ordered sothe smallest is on topcount each wordpush (freq, word) into min-heapif size > k, pop the smallestpop all, then reverseA min-heap of size k keeps the top k without sortingeverythingcompare by freq firsttie → larger word is 'smaller'reverse at the end
The heap keeps only the k best words; the weakest one is always at the top and gets pushed out.
ComplexityTime O(n log k)Space O(n)Counting all words costs O(n); each of the u unique words is pushed and popped on a heap of size at most k, giving O(u log k), and the map of counts needs O(u) space.

What Trips People Up in Real Interviews

1

Clarify tie-breaking rules early—frequency then lexicographical order

2

Mention the time complexity trade-offs between heap and bucket sort

3

Edge case: all words appear exactly once, return lexicographically smallest k

4

Explain why a min-heap is used instead of max-heap for efficiency

5

Discuss how you would modify the solution for streaming data

Solution Code

O(n log k) time
from collections import Counter
import heapq

def topKFrequent(words, k):
    count = Counter(words)
    heap = []
    for word, freq in count.items():
        heapq.heappush(heap, (-freq, word))
    result = []
    for _ in range(k):
        result.append(heapq.heappop(heap)[1])
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Top K Frequent Words problem?

Given an array of words and an integer k, return the k most frequent words. If multiple words have the same frequency, return them in lexicographical order. The solution must run in O(n log k) time.

How do you solve Top K Frequent Words?

The optimal approach runs in O(n log k) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Top K Frequent Words?

Top K Frequent Words is asked at Rippling. It is a medium difficulty problem.

What are common mistakes on Top K Frequent Words?
  • Clarify tie-breaking rules early—frequency then lexicographical order
  • Mention the time complexity trade-offs between heap and bucket sort
  • Edge case: all words appear exactly once, return lexicographically smallest k
  • Explain why a min-heap is used instead of max-heap for efficiency
  • Discuss how you would modify the solution for streaming data