DSA Tracker

Visualize

Top K Frequent Words

Min-heap with lexical tie-break

time O(n log k)space O(k)

The insight is the same as any top-k-by-frequency problem: cap a heap at size k so it only ever holds the strongest k candidates seen so far, evicting the weakest one whenever a stronger candidate arrives — that avoids sorting every distinct word just to find a handful of them. Here "weakest" means lowest frequency first, with alphabetically-later words treated as weaker on a tie, so when two words are equally frequent the one earlier in the alphabet is favored both when the heap has to evict and when the final answer is ordered.

Details

Animated on: Find the k most frequent words, breaking ties by alphabetical order

Problem:Top K Frequent WordsMedium

Pattern:Heap and Top K

Min-heap with lexical tie-break

step 1 / 12

i
[0]
love
[1]
leetcode
[2]
i
[3]
love
[4]
coding
[5]

Process words[0]="i" (1st occurrence). Count map: {i:1}. Highlight current word at index 0.

  • i=0· arr[0] = i
Pseudocode
1FUNCTION topKFrequentWords(words, k):
2  cnt = a lookup table (word → its count)
3  FOR each word w in words: add one to cnt[w]
4  h = a min-heap keyed by count, ties broken alphabetically (weakest on top)
5  FOR each word w in cnt:
6    push (count of w, word w) onto the heap
7    IF heap size > k: pop the weakest (the min)
8  END FOR
9  RETURN the words left in the heap, sorted
10END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 12 steps
  1. Process words[0]="i" (1st occurrence). Count map: {i:1}. Highlight current word at index 0.
  2. Process words[1]="love" (1st occurrence). Count map: {i:1, love:1}. Highlight current word at index 1.
  3. Process words[2]="leetcode" (1st occurrence). Count map: {i:1, love:1, leetcode:1}. Highlight current word at index 2.
  4. Process words[3]="i" (2nd occurrence). Count map: {i:2, love:1, leetcode:1}. i count increases to 2. Highlight current word at index 3.
  5. Process words[4]="love" (2nd occurrence). Count map: {i:2, love:2, leetcode:1}. love count increases to 2. Both i and love have count 2.
  6. Process words[5]="coding" (1st occurrence). Count map complete: {i:2, love:2, leetcode:1, coding:1}. All unique words and their counts finalized.
  7. Add "i" (cnt=2) to min-heap. Heap: [i cnt=2]. Size 1 ≤ k=2. Current heap contains i.
  8. Add "love" (cnt=2) to min-heap. Heap: [i cnt=2, love cnt=2]. Size 2 ≤ k=2. Lexical tie-break: "i" < "love" alphabetically, so "i" ranks first.
  9. Add "leetcode" (cnt=1) to min-heap. Heap: [i cnt=2, love cnt=2, leetcode cnt=1]. Size 3 > k=2. Remove minimum count element: "leetcode" (cnt=1) discarded. Heap: [i cnt=2, love cnt=2].
  10. Add "coding" (cnt=1) to min-heap. Heap: [i cnt=2, love cnt=2, coding cnt=1]. Size 3 > k=2. Remove minimum count element: "coding" (cnt=1) discarded. Final heap: [i, love].
  11. Final answer: ["i", "love"]. Heap contains the 2 most frequent words with counts 2 and 2. Lexical tie-break: "i" < "love" alphabetically, so "i" appears first.
  12. Animation complete. Top k frequent words identified via min-heap with lexical tie-break. Result: ["i", "love"].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Top K Frequent Words in the editorAll Heap problemsBack to roadmap