Heap / Priority Queue crash course ↗ · 183

692. Top K Frequent Words

Return the k most frequent words, sorted by descending count with ties broken lexicographically (smaller word first). Count, then sift the top k with a carefully-ordered size-k min-heapin O(n log k) — the entire trick is the comparator's tie-break.

● MediumHeapBucket SortHash MapTypeScript

PROBLEM What we're solving

Given a list of words and an integer k, return the k most frequent words. The answer must be sorted by frequency from highest to lowest; words with the same frequency are ordered by their lexicographic (alphabetical) order. Example: words = ["i","love","leetcode","i","love","coding"], k = 2 → i and love each appear 2× (everything else 1×), so the answer is ["i", "love"] (i before love alphabetically).

KEY IDEA The tie-break is the whole problem

Insight → counting is trivial; the subtlety is the ordering. Two keys decide who wins: higher frequency first, and on equal frequency the lexicographically smaller word first. To keep only the top k with a size-k min-heap, you must define "smallest" as "the one to evict first": lower frequency is smaller, and on a tie the larger word is smaller so it gets thrown out. Drain the heap (worst-first) and reverse for the final order.

RECIPE Count, sift into a size-k min-heap, drain & reverse

1 · Count. One pass builds a Map<word, count>.
2 · Comparator. Define "a is worse than b" (sinks toward the top of the min-heap) as: freq[a] < freq[b], OR equal frequency AND a > b alphabetically. The worst entry is evicted first.
3 · Sift. Push each distinct word; whenever the heap exceeds size k, pop the worst. The heap settles holding exactly the k best.
4 · Drain & reverse. Popping a min-heap yields entries worst-to-best, so collect them and reverse() to get best-to-worst — the required output order.

Classic confusion → the tie-break flips for the heap. The answer wants ties in ascending alphabetical order, but inside a min-heap you must make the alphabetically largerword compare as smaller, so it's the one evicted when the heap overflows. Get this backwards and you'll keep "banana" over "apple" on a tie. The final reverse() is also easy to forget.

COST Heap vs sort vs bucket

Sort all distinct words

O(n log n)

Count, then sort by (freq desc, word asc), slice k.

Size-k min-heap

O(n log k)

Push each distinct word, evict the worst when size > k.

Three valid approaches

Min-heap (optimal for small k): count, then push the distinct words into a size-k min-heap whose comparator evicts lower-frequency (and, on ties, alphabetically-larger) words. Each of the d distinct words costs O(log k), so it's O(n + d log k) ≈ O(n log k). Drain the heap and reverse.

Sort: the simplest correct idea — dump the distinct words into an array, sort by frequency descending then word ascending, and take the first k. Easy to write but O(n log n).

Bucket sort: bucket words by their count (counts are bounded by n), then walk buckets high → low; inside each bucket sort the tied words alphabetically. O(n + n log n) in the worst case because of the within-bucket sorts.

Pattern transfer → the size-k min-heap with a custom comparator generalizes to Top K Frequent Elements, K Closest Points to Origin, and Kth Largest Element. The "multi-key sort, then flip one key for the heap" trick recurs anywhere ties must break opposite to the primary order.

RUN IT Count, sift a size-k min-heap, drain & reverse

words =k =

step 0 / 17

STARTFind the 2 most frequent words (ties broken alphabetically). Phase 1: count every word in one pass.

1▶function topKFrequent(words: string[], k: number): string[] {
2  // 1) Count every word in one pass.
3▶  const freq = new Map<string, number>();
4  for (const w of words) {
5    freq.set(w, (freq.get(w) ?? 0) + 1);
6  }
7 
8  // 2) Size-k MIN-heap. The "smallest" entry is the one we want to
9  //    evict first: lower frequency loses; on a tie, the
10  //    LEXICOGRAPHICALLY LARGER word loses (so it sinks to the top).
11  const worseThan = (a: string, b: string): boolean =>
12    freq.get(a)! < freq.get(b)! ||
13    (freq.get(a)! === freq.get(b)! && a > b);
14 
15  const heap: string[] = []; // binary min-heap kept at <= k entries
16  const up = (i: number) => {
17    while (i > 0) {
18      const p = (i - 1) >> 1;
19      if (!worseThan(heap[i], heap[p])) break;
20      [heap[i], heap[p]] = [heap[p], heap[i]];
21      i = p;
22    }
23  };
24  const down = (i: number) => {
25    const n = heap.length;
26    for (;;) {
27      let s = i;
28      const l = 2 * i + 1, r = 2 * i + 2;
29      if (l < n && worseThan(heap[l], heap[s])) s = l;
30      if (r < n && worseThan(heap[r], heap[s])) s = r;
31      if (s === i) break;
32      [heap[i], heap[s]] = [heap[s], heap[i]];
33      i = s;
34    }
35  };
36 
37  for (const w of freq.keys()) {
38    heap.push(w);
39    up(heap.length - 1);
40    if (heap.length > k) {        // overflow: drop the worst entry
41      [heap[0], heap[heap.length - 1]] = [heap[heap.length - 1], heap[0]];
42      heap.pop();
43      down(0);
44    }
45  }
46 
47  // 3) Heap holds the k best, worst-first. Pop all, then reverse.
48  const res: string[] = [];
49  while (heap.length) {
50    res.push(heap[0]);
51    heap[0] = heap[heap.length - 1];
52    heap.pop();
53    down(0);
54  }
55  return res.reverse();
56}

wordsi0love1leetcode2i3love4coding5

State

{}

freq

(empty)

heap

current wordfrequency mapheap root (worst / evicted)heap entryresult

slowfast

TYPESCRIPT The solution, annotated

topKFrequent.ts
function topKFrequent(words: string[], k: number): string[] {
  // 1) Count every word in one pass.
  const freq = new Map<string, number>();
  for (const w of words) {
    freq.set(w, (freq.get(w) ?? 0) + 1);
  }

  // 2) Size-k MIN-heap. The "smallest" entry is the one we want to
  //    evict first: lower frequency loses; on a tie, the
  //    LEXICOGRAPHICALLY LARGER word loses (so it sinks to the top).
  const worseThan = (a: string, b: string): boolean =>
    freq.get(a)! < freq.get(b)! ||
    (freq.get(a)! === freq.get(b)! && a > b);

  const heap: string[] = []; // binary min-heap kept at <= k entries
  const up = (i: number) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!worseThan(heap[i], heap[p])) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const down = (i: number) => {
    const n = heap.length;
    for (;;) {
      let s = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && worseThan(heap[l], heap[s])) s = l;
      if (r < n && worseThan(heap[r], heap[s])) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  };

  for (const w of freq.keys()) {
    heap.push(w);
    up(heap.length - 1);
    if (heap.length > k) {        // overflow: drop the worst entry
      [heap[0], heap[heap.length - 1]] = [heap[heap.length - 1], heap[0]];
      heap.pop();
      down(0);
    }
  }

  // 3) Heap holds the k best, worst-first. Pop all, then reverse.
  const res: string[] = [];
  while (heap.length) {
    res.push(heap[0]);
    heap[0] = heap[heap.length - 1];
    heap.pop();
    down(0);
  }
  return res.reverse();
}

Reading it block by block

Lines 2–6 — count. A single pass over words builds a Map from each word to its frequency. The ?? 0 seeds first-time keys.

Lines 11–13 — the comparator (the crux). worseThan(a, b) is true when a should sink toward the top of the min-heap (i.e. be evicted first): lower frequency, or — on equal frequency — the alphabetically larger word. This flips the tie-break versus the final answer on purpose.

Lines 15–40 — the heap helpers. upsifts a freshly-pushed entry toward the root while it's "worse than" its parent; down sinks the root after we replace it. Both compare with worseThan, so the root is always the single entry we most want to discard.

Lines 42–50 — sift the top k. Push each distinct word and sift it up. Whenever the heap exceeds k, swap the worst (root) to the end, pop it, and sink the new root. The heap is invariably the k best seen so far.

Lines 53–61 — drain and reverse. Repeatedly popping the min-heap emits entries from worst to best, so collect them and reverse() to produce the required frequency-descending, alphabetically-ascending order.

Complexity → Counting is O(n). With d distinct words, each heap push/evict is O(log k), so sifting is O(d log k) and draining is O(k log k); total O(n + d log k) ≈ O(n log k) time and O(n) space (the count map). The pure-sort approach is O(n log n) time.

INTERVIEWFollow-ups they'll ask

"Why is the heap comparator's tie-break reversed?"The answer wants ties in ascending order, but a min-heap evicts its "smallest," so the larger word must compare as smaller to be the one thrown away.
"Do it without a heap." Sort the distinct words by (freq desc, word asc) and take the first k — O(n log n).
"Can you get O(n)?"Bucket by frequency, but you still pay to sort tied words within a bucket, so it's O(n log n) worst case unless ties are rare.
"Streaming words?" Maintain the running count map plus the size-k heap; re-sift a word when its frequency changes (or accept approximate top-k via Count-Min Sketch).
"Forgot the final reverse — what breaks?"You'd return the k answers in exactly the wrong order (least frequent / alphabetically last first).

OPTIMAL Heap

topKFrequent.ts
function topKFrequent(words: string[], k: number): string[] {
  // 1) Count every word in one pass.
  const freq = new Map<string, number>();
  for (const w of words) {
    freq.set(w, (freq.get(w) ?? 0) + 1);
  }

  // 2) Size-k MIN-heap. The "smallest" entry is the one we want to
  //    evict first: lower frequency loses; on a tie, the
  //    LEXICOGRAPHICALLY LARGER word loses (so it sinks to the top).
  const worseThan = (a: string, b: string): boolean =>
    freq.get(a)! < freq.get(b)! ||
    (freq.get(a)! === freq.get(b)! && a > b);

  const heap: string[] = []; // binary min-heap kept at <= k entries
  const up = (i: number) => {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!worseThan(heap[i], heap[p])) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const down = (i: number) => {
    const n = heap.length;
    for (;;) {
      let s = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && worseThan(heap[l], heap[s])) s = l;
      if (r < n && worseThan(heap[r], heap[s])) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  };

  for (const w of freq.keys()) {
    heap.push(w);
    up(heap.length - 1);
    if (heap.length > k) {        // overflow: drop the worst entry
      [heap[0], heap[heap.length - 1]] = [heap[heap.length - 1], heap[0]];
      heap.pop();
      down(0);
    }
  }

  // 3) Heap holds the k best, worst-first. Pop all, then reverse.
  const res: string[] = [];
  while (heap.length) {
    res.push(heap[0]);
    heap[0] = heap[heap.length - 1];
    heap.pop();
    down(0);
  }
  return res.reverse();
}

ALT 1 Sort — count then sort by (freq desc, word asc)

O(n log n) time · O(n) space

The most direct correct approach: tally every word, sort the distinct words by descending frequency with ties broken alphabetically, and slice off the first k. No heap, and the comparator reads exactly like the required answer order.

approach-2.ts
function topKFrequent(words: string[], k: number): string[] {
  // 1) Count every word in one pass.
  const freq = new Map<string, number>();
  for (const w of words) {
    freq.set(w, (freq.get(w) ?? 0) + 1);
  }

  // 2) Sort distinct words: higher frequency first, ties alphabetical.
  const distinct = [...freq.keys()];
  distinct.sort((a, b) =>
    freq.get(b)! - freq.get(a)! || (a < b ? -1 : a > b ? 1 : 0),
  );

  // 3) The first k are the answer, already in the required order.
  return distinct.slice(0, k);
}

Note → Simplest to write and the comparator matches the spec directly (no tie-break flip), but the sort over all distinct words dominates at O(n log n). When k is small relative to the number of distinct words, the size-k min-heap is faster at O(n log k).

ALT 2 Bucket sort by frequency, sort within buckets

O(n log n) worst case · O(n) space

Counts are bounded by n, so bucket words by their frequency and walk buckets from highest to lowest; sort each bucket's tied words alphabetically before harvesting.

approach-3.ts
function topKFrequent(words: string[], k: number): string[] {
  const freq = new Map<string, number>();
  for (const w of words) freq.set(w, (freq.get(w) ?? 0) + 1);

  // buckets[c] = all words seen exactly c times.
  const buckets: string[][] = Array.from({ length: words.length + 1 }, () => []);
  for (const [w, c] of freq) buckets[c].push(w);

  const res: string[] = [];
  for (let c = buckets.length - 1; c >= 1 && res.length < k; c--) {
    if (buckets[c].length === 0) continue;
    buckets[c].sort();            // ties: lexicographic ascending
    for (const w of buckets[c]) {
      res.push(w);
      if (res.length === k) return res;
    }
  }
  return res;
}

Note → The bucket walk is O(n), but sorting tied words inside buckets makes the worst case O(n log n). It avoids any heap bookkeeping and is clean when ties are few.

MNEMONIC The one-liner

"Count, push into a size-k min-heap that evicts low-freq (ties: bigger word loses), drain, reverse."

TRIGGERS When you see _ → reach for _

"k most frequent words"	count map → size-k min-heap (O(n log k))
ties broken alphabetically	flip tie-break in the min-heap comparator
want the simplest correct code	sort by (freq desc, word asc), take k
"top k" / "k closest" / "kth largest"	size-k heap, evict the worst

SKELETON The reusable shape

skeleton.ts
const freq = new Map<string, number>();
for (const w of words) freq.set(w, (freq.get(w) ?? 0) + 1);

// min-heap: evict lower freq first; on a tie, evict the LARGER word
const worse = (a, b) =>
  freq.get(a)! < freq.get(b)! ||
  (freq.get(a)! === freq.get(b)! && a > b);

const heap = []; // keep size <= k
for (const w of freq.keys()) {
  push(w);                 // sift up by 'worse'
  if (heap.length > k) popMin(); // drop the worst
}
return drainAll().reverse();     // worst-first -> best-last -> reverse

FLASHCARDS Tap to flip

What two keys order the answer?

Frequency descending; ties broken by lexicographic (ascending) order.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

How are words with the same frequency ordered in the answer?

QUESTION 02

Optimal time complexity with the size-k heap approach?

QUESTION 03

In the size-k MIN-heap, which entry is at the root (evicted on overflow)?

QUESTION 04

Why must the heap comparator break ties opposite to the final answer?

QUESTION 05

After the heap settles on the k best, what gives the correct output order?

QUESTION 06

words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 returns:

QUESTION 07

For the pure-sort approach, the comparator over distinct words is:

QUESTION 08

#692 · Top K Frequent WordsReturn the k most frequent words with ties broken lexicographically. A size-k min-heap whose comparator evicts the lower frequency first and, on a tie, the lexicographically larger word keeps the answer in O(n log k).Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA The tie-break is the whole problem

RECIPE Count, sift into a size-k min-heap, drain & reverse

COST Heap vs sort vs bucket

Three valid approaches

RUN IT Count, sift a size-k min-heap, drain & reverse

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Heap

ALT 1 Sort — count then sort by (freq desc, word asc)

ALT 2 Bucket sort by frequency, sort within buckets

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _