Abstract / Summary

Sort the array by how often each number appears, putting numbers with lower frequency first.

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 81% (400k+ submissions).

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 frequencySort that reorders an input list of integers according to two criteria: numbers that appear less frequently are placed before those that appear more frequently, and among numbers with the same frequency, larger values come first. The method returns a new list reflecting this ordering.

Frequency Counting

The first logical block builds a frequency map for the elements in the input list. A defaultdict of integers is used so that each unseen key is automatically initialized to zero before being incremented.

freq = defaultdict(int)
for n in nums:
    freq[n] += 1

This approach guarantees that every integer in nums is accounted for exactly once per occurrence, handling empty inputs gracefully because the loop simply does not execute.

Tuple Construction

After the frequencies are known, the code creates a list of two-element tuples. Each tuple contains the frequency of a distinct number and the number itself. The comprehension iterates over the keys of the frequency dictionary.

all = [(freq[f], f) for f in freq]

By storing both pieces of information together, the subsequent sorting step can access both the frequency and the value without additional lookups.

Sorting Logic

The list of tuples is sorted with a custom key function. The key multiplies the frequency by a large constant (1000) and then subtracts the value. Because Python’s sort is stable and sorts in ascending order, this expression yields the desired ordering: lower frequencies produce smaller keys, and for equal frequencies the subtraction of a larger value results in a smaller key, thereby placing larger numbers earlier.

all.sort(key=lambda x: x[0] * 1000 - x[1])

The constant 1000 is chosen to dominate the value component, ensuring that frequency differences outweigh value differences. This technique avoids the need for a tuple-based key and reduces the overhead of constructing intermediate comparison objects.

Result Assembly

The final phase expands each tuple back into the output list. For each (frequency, number) pair, the number is repeated frequency times and concatenated to the result list using the += operator with a list literal.

result = []
for f, n in all:
    result += [n] * f
return result

Repeating the number with list multiplication is efficient because it creates the required sublist in a single operation, and the += concatenation updates the result list in place.

Edge Cases Handled

The algorithm naturally accommodates several edge conditions:

• An empty input list produces an empty frequency map, an empty tuple list, and ultimately returns an empty list without error.
• Input lists containing a single distinct value generate a single tuple with its full count, and the result list reproduces the original list unchanged.
• Lists where all elements are identical result in a single tuple whose frequency equals the length of the input; the sorting step leaves the order unchanged because there is only one tuple.
• Negative integers are treated identically to positive ones because the frequency map keys are the raw integer values, and the sorting key arithmetic works with signed numbers.
• Very large integer values are handled correctly because the multiplication by 1000 and subtraction are performed using Python’s arbitrary-precision arithmetic, preventing overflow.

Performance Optimizations

The code exhibits several deliberate choices that improve runtime efficiency:

• Using defaultdict(int) eliminates the need for explicit existence checks when updating frequencies, reducing conditional overhead inside the counting loop.
• Constructing the list of tuples via a comprehension creates the data structure in a single pass, avoiding multiple appends.
• The custom sort key combines both sorting criteria into a single integer expression, allowing the built-in Timsort algorithm to compare simple integers rather than tuples, which can be marginally faster.
• List multiplication [n] * f generates the repeated segment in one operation, avoiding a manual inner loop that would append the same element repeatedly.
• The += operator on the result list extends it in place, which is more efficient than repeatedly calling append inside a nested loop.

Overall, the implementation leverages Python’s built-in data structures and idioms to achieve a concise solution that respects the required ordering while maintaining good performance characteristics.

Imagine having a big box filled with colorful building blocks, where some colors appear only once or twice, and others appear many times. This piece of computer code is like a special toy sorting machine that looks at all the blocks and arranges them in a very specific order.

The machine first makes a list to count how many blocks of each color are in the pile. It keeps a note of these counts so it knows exactly how many reds or blues there are sitting in front of it.

Next, the machine looks at all the different types of blocks. It decides to put the ones that appear the fewest times at the very front of the line. If two types of blocks appear the same number of times, it chooses to put the one with the biggest number value first. Think of this like putting the rarest toys on display before the common ones.

Finally, the machine starts building a new line. It looks at the sorted list of types and their counts, grabs the exact number of blocks for each type, and places them into a new, organized row. The result is a neat sequence where everything is grouped by how often it shows up, moving from the lonely items to the very popular ones.

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	JS	Java		Go			Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem					Ruby
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM							C#
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python

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