Skip to main content

22. Top K Frequent Words

mediumAsked at GitLab

Return the k most frequent words, breaking frequency ties alphabetically.

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

Problem

Given a list of words and an integer k, return the k most frequent words sorted by frequency descending; words with the same frequency are returned in lexicographic ascending order.

Constraints

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • 1 <= k <= unique-word-count

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 fully sort

Bucket counts, sort all unique words by (-count, word), take first k.

Time
O(u log u)
Space
O(u)
const c={}; for (const w of words) c[w]=(c[w]||0)+1;
return Object.keys(c).sort((a,b)=> c[b]-c[a] || a.localeCompare(b)).slice(0,k);

Tradeoff:

2. Min-heap of size k

Push every (count, word) into a min-heap whose ordering puts least-frequent on top with reversed alpha for ties; pop when size exceeds k; finally dump and reverse.

Time
O(u log k)
Space
O(u)
function topKFrequent(words, k){
  const c = new Map();
  for (const w of words) c.set(w, (c.get(w) || 0) + 1);
  const cmp = (a, b) => a[0] === b[0] ? b[1].localeCompare(a[1]) : a[0] - b[0];
  const h = [];
  const up = i => { while (i){ const p = (i-1)>>1; if (cmp(h[p], h[i]) <= 0) break;
    [h[p], h[i]] = [h[i], h[p]]; i = p; } };
  const down = i => { const n = h.length; while (true){
    const l = 2*i+1, r = 2*i+2; let m = i;
    if (l < n && cmp(h[l], h[m]) < 0) m = l;
    if (r < n && cmp(h[r], h[m]) < 0) m = r;
    if (m === i) break; [h[m], h[i]] = [h[i], h[m]]; i = m; } };
  for (const [w, n] of c){ h.push([n, w]); up(h.length - 1);
    if (h.length > k){ h[0] = h.pop(); down(0); } }
  const out = [];
  while (h.length){ out.push(h[0][1]); h[0] = h.pop(); if (h.length) down(0); }
  return out.reverse();
}

Tradeoff:

GitLab-specific tips

GitLab leans on this to gauge whether you can stream the top-k slowest jobs across a runner pool without re-sorting the whole telemetry table on each tick.

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 GitLab interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →