Abstract / Summary

Given an array of integers, repeatedly replace the largest value with its difference from the next largest until all values are equal, and find the minimum number of operations needed.

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 73% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• 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 solves the problem of counting the minimum number of reduction operations required to make all elements of an integer array equal. It does so by first building a frequency map of the distinct values, then processing the values in descending order while accumulating the number of operations needed. The algorithm relies on the observation that each distinct value must be reduced to the next smaller distinct value, and the total operations can be expressed as a cumulative sum of frequencies.

Key Steps

Frequency Counting

The first phase iterates over the input list and records how many times each integer appears. A dictionary with default integer values is used, which automatically creates a zero entry for unseen keys and increments the count for each element.

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

This step transforms the original list into a compact representation that captures the essential information needed for the subsequent reduction calculations.

Sorting Distinct Values

After the frequencies are known, the distinct keys are extracted and sorted in ascending order. The sorted list enables a straightforward reverse traversal from the largest value down to the second smallest, which mirrors the direction of reduction operations.

keys = sorted(freq)

The sorted order is crucial because the algorithm aggregates the effect of reducing larger numbers onto smaller ones, and the reverse iteration guarantees that each step has access to the cumulative count of elements that have already been considered.

Accumulating the Result

The core loop walks through the sorted keys in reverse, skipping the smallest key because it does not need to be reduced further. Two accumulator variables are maintained: result, which stores the total number of operations, and again, which tracks the cumulative frequency of all values processed so far. For each key k, the algorithm adds the current frequency plus the cumulative count (again) to result, then updates again by adding the current frequency. This reflects that every element with value k must be reduced once, and all previously processed elements will also be reduced again when moving to the next smaller distinct value.

result = 0
again  = 0
for k in reversed(keys[1:]):
    result += freq[k] + again
    again  += freq[k]

When the loop finishes, result holds the total number of reduction operations required to make all numbers equal to the smallest value in the original array.

Edge Cases Handled

The algorithm gracefully handles several edge conditions without additional branching logic. When the input list contains a single distinct value, the sorted keys list has length one, and the reverse slice keys[1:] yields an empty sequence. Consequently, the loop body is never executed, leaving result at its initial value of zero, which correctly represents that no reductions are needed. If the input list is empty, the frequency map remains empty, the sorted keys list is empty, and the same empty slice ensures that the loop does not run, again returning zero. The use of defaultdict(int) guarantees that any attempt to access a missing key yields a default count of zero, preventing key-error exceptions during the accumulation phase.

Performance Optimizations

The implementation leverages a few implicit optimizations that contribute to its efficiency. By constructing a frequency map, the algorithm reduces the problem size from potentially n elements to at most the number of distinct values, which is often much smaller. This compression eliminates the need to process each element repeatedly during the reduction phase. Sorting the distinct keys is performed only once, and the subsequent reverse iteration works directly on the sorted list without additional data structures. The cumulative variables result and again are updated in constant time per distinct key, avoiding nested loops or repeated scans of the original array. The overall flow consists of a linear pass to build frequencies, a sort whose cost is bounded by the number of unique values, and a linear pass over those unique values, resulting in a streamlined execution path.

Imagine a big pile of colorful building blocks of different sizes. To play this game, the goal is to make all the blocks the same size.

First, the computer looks at all the blocks and makes a list of every size it sees, keeping track of how many blocks there are for each one. Think of this like putting all the small blocks in one basket, the medium blocks in another, and the big blocks in a third basket.

Next, the computer sorts the sizes from smallest to biggest, just like lining up toys from tiny to giant. It starts with the biggest blocks and turns them into the size just below them. If there are ten giant blocks, it takes all ten and changes them. Then, it looks at the next set of big blocks. Because those giant ones already changed, they have to change again, so the new group has to count the ones that already moved. It keeps doing this, moving all the blocks down to the next size, until every single block in the pile is the same tiny size as the very first one. Every time a block changes, it counts as one step, and those steps are all added up at the end to see how busy the computer was.

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

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