Top K Frequent Words – Solution & Complexity
Solution Walkthrough
Step 1: Count first, because ranking is based only on frequencies
- The raw array may contain many repeated words, but only distinct words matter once you know how often each one appears.
- Build a hash map from word to frequency.
- After that, every solution is just a different way to rank those distinct words by the required key:
(-frequency, word).
Step 2: Straightforward approach: count everything, then sort all distinct words
- Count each word in a hash map.
- Put the distinct words into an array.
- Sort that array by frequency descending, then by lexicographic ascending order.
- Return the first
kwords. - This is simple and deterministic, but it sorts all
mdistinct words, so it costsO(m log m)after counting.
Step 3: Optimized final approach: keep only the best k words in a heap
- Count frequencies exactly as before.
- Maintain a min-heap of size at most
kwhose root is the current worst candidate among the kept topkwords. - "Worse" means lower frequency, or on a frequency tie, lexicographically larger.
- Whenever the heap grows past
k, remove that worst candidate. - At the end, sort the remaining heap entries back into the required final order: frequency descending, lexicographic ascending.
- This reduces the ranking phase to
O(m log k)when there aremdistinct words.
Step 4: Watch the tie-break carefully
- Many wrong answers count frequencies correctly but forget that ties must be resolved by lexicographic ascending order.
- That tie-break is required even in the heap version, so your heap comparator and your final output order must agree.
- Because comparison is case-sensitive,
"Apple" < "apple"and"Cherry" < "banana"under ordinary string ordering.
Step 5: Final complexity
Counting takes
O(n)over the original array, and the heap-based ranking takesO(m log k)over themdistinct words. The auxiliary space isO(m + k)for the frequency map and heap.
