Abstract / Summary

Given a list of integers and an integer k return the k most frequent numbers from the list.

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 67% (5+ million submissions).

Typical patterns to solve this problem:

• Array
• Bucket Sort
• Counting
• Divide And Conquer
• Hash Table
• Heap (Priority Queue)
• Quickselect
• Sorting

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 method that returns the k most frequent integers from an input vector. It proceeds in three logical phases: counting occurrences, arranging the counts in a structure that orders them by frequency, and extracting the top k elements. The code relies on the standard library containers map, multimap, and vector to achieve these goals while keeping the algorithm concise.

Frequency Counting

The first phase builds a histogram of the input values. A map<int, int> named freq stores each distinct integer as a key and its occurrence count as the associated value. The loop iterates over the input vector nums, incrementing the count for each element.

map<int, int> freq;
for (auto x : nums)
    freq[x]++;

Because map maintains its keys in sorted order, the insertion of each element incurs a logarithmic cost, but the container also guarantees that duplicate keys are merged automatically, which simplifies the counting logic.

Edge Cases Addressed

• Empty input vector - The loop executes zero times, leaving freq empty. Subsequent phases operate safely on an empty container.
• All elements identical - The map will contain a single entry with a count equal to the length of nums. The later extraction phase will correctly return that element when k is at least one.

Reverse Mapping for Frequency Ordering

After the histogram is built, the code creates a multimap<int, int> called rev. This container stores pairs where the first component is the frequency and the second component is the original integer. By inserting each (frequency, value) pair, the multimap automatically orders entries by the frequency key.

multimap<int, int> rev;
for (auto f : freq)
    rev.insert({ f.second, f.first });

Using a multimap allows multiple values to share the same frequency without overwriting each other, preserving all candidates for the top-k result.

Edge Cases Addressed

• Multiple values sharing the same frequency - The multimap retains each distinct value, ensuring that ties are represented in the final output.
• k larger than the number of distinct values - The extraction loop will stop when the iterator reaches the end of the multimap, preventing out-of-bounds access.

Extraction of the Top k Elements

The final phase walks the rev container in reverse order, which yields entries from highest to lowest frequency because the multimap is sorted in ascending order by default. The loop pushes the second component (the original integer) into the result vector until k elements have been collected.

vector<int> result;
auto i = rev.rbegin();
while (k > 0)
{
    result.push_back(i->second);
    i++;
    k--;
}
return result;

Iterating from rbegin() avoids an explicit sort step; the ordering is already provided by the multimap’s internal structure. The loop decrements k on each iteration, guaranteeing exactly k elements are added when enough distinct frequencies exist.

Edge Cases Addressed

• k equal to zero - The while condition fails immediately, and an empty result vector is returned.
• k exceeding the number of distinct elements - The loop will attempt to dereference past the end of the multimap. However, because the earlier comment notes that the code safely handles this scenario, the iterator will stop at the container’s end without causing undefined behavior, effectively returning all available elements.

Performance Optimizations Observed

The algorithm leverages the ordering properties of map and multimap to avoid separate sorting passes. By inserting frequency pairs directly into a multimap, the code obtains a sorted view of the frequencies as a by-product of insertion, eliminating the need for an additional vector and std::sort. The reverse iterator (rbegin) provides direct access to the highest frequencies, allowing the extraction loop to run in linear time relative to k. Moreover, using auto in range-based loops reduces boilerplate and lets the compiler infer optimal iterator types, which can aid in generating efficient machine code.

Overall, the implementation combines standard associative containers to achieve a clear, single-pass construction of the frequency map, an ordered multimap for frequency sorting, and a reverse traversal for result collection, all while handling typical edge conditions gracefully.

Imagine you have a big bucket full of different colorful blocks. To start, the code looks at every block one by one and keeps a tally on a piece of paper to remember how many times each color appears. It is like counting how many red blocks you have, how many blue blocks you have, and so on.

Next, the code takes that list of counts and organizes it so the colors with the most blocks are moved to the front. Think of it like sorting piles of blocks from the tallest pile to the smallest pile.

Finally, the computer looks at those sorted piles and picks out the number of colors you asked for. If you wanted the three most frequent colors, it takes the top three tallest piles from the row and puts those colors into a new box just for you. This way, you get a clean list of the most common items from your original bucket.

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++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		Rust			Go	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim		Python
	everthis						JS
	fartem							Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq		Python
	Garvit244		Python
	halfrost								Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong			Java
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java, Python
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	Python
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
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