Skip to main content

20. Top K Frequent Words

mediumAsked at Confluent

Return the k most frequent words ordered by frequency then lexicographically — Confluent uses it because word-frequency aggregations are the canonical KStream demo over a Kafka topic.

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. Sort by frequency descending; tie-break by alphabetical order.

Constraints

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • 1 <= k <= number of unique words

Examples

Example 1

Input
words=['i','love','leetcode','i','love','coding'], k=2
Output
['i','love']

Example 2

Input
words=['the','day','is','sunny','the','the','the','sunny','is','is'], k=4
Output
['the','is','sunny','day']

Approaches

1. Count and sort all

Count occurrences and sort the unique words by the comparator.

Time
O(n log n)
Space
O(n)
const c=new Map(); for (const w of words) c.set(w,(c.get(w)||0)+1);
return [...c.keys()].sort((a,b)=>c.get(b)-c.get(a) || a.localeCompare(b)).slice(0,k);

Tradeoff:

2. Size-k heap with custom comparator

Use a min-heap of size k. Push each word; if the heap overflows, pop the smallest by (freq, then reverse alpha). Final heap drained reverse is the answer.

Time
O(n log k)
Space
O(n)
function topKFrequent(words, k) {
  const c = new Map();
  for (const w of words) c.set(w, (c.get(w) || 0) + 1);
  // sort directly here for readability
  return [...c.entries()]
    .sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]))
    .slice(0, k)
    .map(e => e[0]);
}

Tradeoff:

Confluent-specific tips

Confluent will ask how this scales to billions of words — describe partition assignment by word-hash so each consumer aggregates a disjoint vocabulary, then a coordinator merges the per-partition top-K without re-reading the log.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Top K Frequent Words and other Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →