Top K Frequent Words
Rank the hottest words in a search log. Every query in the log is one lowercase word. Return the k words that show up most often, the most frequent first. When two words show up equally often, the one that comes first in alphabetical order goes first, so "ap" comes before "app", and "app" before "apple". Limits: 1 to 300,000 words, each 1 to 10 lowercase letters, and k is at least 1 and at most the number of different words. Counting each word by scanning the whole log is far too slow at that size. Think about: how do you get every word's count in one pass? And what does ordering by count alone do with the words that tie? Example: ["mug","tea","mug","jar","tea","pan"], k = 3 => ["mug","tea","jar"] (mug and tea appear twice, jar and pan once, and jar sorts before pan)
You're building a trending list from a long log of search words and you want the k that show up most. Interviewers love it because counting is the easy half, and the real test is the ordering: equal counts must come out alphabetically, which a heap that only compares counts quietly gets wrong. The classic trap is rescanning the whole log to count each word, which crawls on a big feed. Expect up to 300,000 words of 1 to 10 lowercase letters, and k never exceeds the number of different words.
Examples
You write
top_k_frequent_words(words: List[str], k: int)
Example 1
- Input
- words = ["mug","tea","mug","jar","tea","pan"], k = 3
- returns
- ["mug","tea","jar"]
Example 2
- Input
- words = ["a"], k = 1
- returns
- ["a"]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Top K Frequent Words ready to code. It is free, and the editor needs no account.
The pattern behind it
Arrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problemsHeaps
I reach for it when
- You need the k largest or k smallest items.
- You repeatedly take the best remaining item.
Say this before you type. Say what the heap holds, how big it stays, and what sits on top.
All 22 Heaps problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.