Abstract / Summary

Given a list of words and a number k, return the k most frequent words sorted by frequency then alphabetically.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Bucket Sort
• Counting
• Hash Table
• Heap (Priority Queue)
• Sorting
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method topKFrequent that receives a list of words and an integer k. Its purpose is to return the k most frequent words ordered first by descending frequency and then alphabetically for ties. The algorithm proceeds in three phases: counting occurrences, grouping words by their frequencies, and assembling the final ordered list.

Key Steps

The first phase builds a frequency map using a defaultdict of integers. Each word from the input list increments its counter.

all = defaultdict(int)

for w in words:
    all[w] += 1

The second phase creates an inverted index that maps each distinct frequency to a list of words that share that count. This structure enables easy traversal from the highest frequency downwards.

invert = defaultdict(list)
for a in all:
    invert[all[a]].append(a)

The third phase iterates over the frequencies in descending order, sorts the associated word lists alphabetically, and concatenates them into a single result list. Finally, the method slices the first k elements to produce the answer.

result = []
for i in sorted(invert, reverse=True):
    result += sorted(invert[i])

return result[:k]

Edge Cases Handled

When the input contains duplicate words, the frequency map correctly aggregates their counts, ensuring that each word appears only once in the inverted index. If multiple words share the same frequency, the explicit alphabetical sort (sorted(invert[i])) guarantees a deterministic ordering that matches the required tie-breaking rule. The slicing operation (result[:k]) gracefully handles cases where k exceeds the number of distinct words, returning all available entries without raising an error.

The use of defaultdict for both the frequency map and the inverted index eliminates the need for explicit existence checks, thereby handling empty inputs and unseen keys without additional conditional logic.

Performance Optimizations

The algorithm leverages defaultdict to achieve constant-time updates when counting word occurrences, avoiding the overhead of key existence checks. By grouping words by frequency before sorting, the code reduces the number of sort operations: each group is sorted only once, and the outer loop processes frequencies in descending order using sorted(invert, reverse=True). This approach prevents repeated sorting of the entire word list and confines alphabetical ordering to the relatively small groups of words that share the same count.

The final concatenation (result += sorted(invert[i])) builds the answer incrementally, allowing the method to stop after the required k elements are collected, which can save work when k is much smaller than the total number of distinct words. The slice operation ensures that any excess elements generated during the loop are discarded efficiently.

Imagine having a big box filled with many different colored building blocks. This code starts by picking up each block one by one and writing down how many times each specific color appears. It uses a helpful list to keep track of these counts.

Next, it gathers all the blocks together based on how often they showed up. It puts the blocks that appear the most times in one pile and the ones that appear less often in other piles.

Then, it organizes these piles from the most common colors to the rarest colors. If some colors appear the same number of times, it sorts them alphabetically like words in a dictionary. Finally, it looks at this sorted line of colors and picks out the number of favorite blocks requested.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java					Python			TS
	WalkCCC	C++	Java					Python
	leetcode.ca	C++	Java					Python		Go	TS
	LeetcodeHelp	C++	Java					Python
	MemoryLimitExceeded	C++						Python
	Progiez	C++	Java					Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem						Ruby
	fengvyi	C++
	fsq	C++
	gouthampradhan		Java
	halfrost									Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007							Python
	MacJim	C++
	qiyuangong		Java
	ruoru					Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28		Java
	vthwang		Java
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
MacJim	C++
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality