Abstract / Summary

Make all numbers in the array different by increasing some values as little as possible.

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

Typical patterns to solve this problem:

• Array
• Counting
• Greedy
• 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 making all elements in an integer array distinct by incrementing values the minimal total number of times. The algorithm works by first ordering the input, then walking through the sorted values while tracking the smallest permissible value for the next element. Whenever a current element is smaller than this permissible value, the difference is added to the result as the required number of increments. The permissible value is then advanced to one more than the larger of the current element and the previous permissible value.

Key Steps

Sorting the Input

nums.sort()

Sorting places the numbers in non-decreasing order, which guarantees that any duplicate or smaller value will appear consecutively. This ordering is essential for the greedy approach that follows, because it allows the algorithm to decide locally for each element whether it needs to be increased.

Initializing the Tracking Variables

result = 0
next = -1

result accumulates the total increments performed. next represents the smallest integer that the upcoming element is allowed to take while preserving uniqueness. Starting with -1 ensures that the first element, regardless of its value, will be accepted without increment.

Iterating Over the Sorted Numbers

for n in nums:
    if n < next:
        result += next - n
    next = 1 + max(next, n)

During each iteration the algorithm compares the current number n with next.

• If n is already at least next, no increment is needed and result remains unchanged.
• If n is smaller than next, the difference next - n is the exact amount required to raise n to next, and this amount is added to result.

After handling the possible increment, next is updated to one more than the larger of the current next and the current number n. This update guarantees that the following element must be strictly greater than any value already assigned, preserving uniqueness.

Returning the Accumulated Cost

return result

The final value of result reflects the minimal total number of increments needed to transform the original array into a set of unique integers.

Edge Cases Handled

When the input array is empty, the for loop never executes, leaving result at its initial value of 0. The function correctly returns 0, indicating that no increments are required.

If the array contains a single element, the sorted list has one entry. Since next starts at -1, the condition n < next is false for any non-negative integer, and the algorithm simply sets next to n + 1. The returned result remains 0, as no change is needed.

For arrays where all elements are identical, the first occurrence is accepted as is, and each subsequent duplicate triggers the if n < next branch. The difference added each time grows by one, producing the sequence of increments needed to spread the duplicates into consecutive integers.

When the array already consists of strictly increasing values, the condition n < next never holds, and result stays 0. The algorithm efficiently recognizes that no work is required.

Performance Optimizations

The algorithm achieves efficiency by performing a single sort followed by a linear scan. Sorting is the dominant operation, but it is performed once, and the subsequent loop runs in O(n) time, where n is the length of the input list.

Within the loop, the use of max(next, n) avoids an explicit conditional to decide whether to advance next based on the current number. This single expression reduces branching and keeps the inner loop body minimal.

Updating next with 1 + max(next, n) ensures that the permissible value always moves forward, eliminating the need for additional data structures such as hash sets or frequency arrays. The algorithm therefore uses only a constant amount of extra memory beyond the input list itself.

By relying on the sorted order, the code sidesteps the need for repeated searches for the next free integer, which would be costly in a naïve implementation. The greedy choice of always moving to the smallest possible unique value guarantees minimal total increments while maintaining a simple and fast execution path.

Imagine you have a big box of numbered blocks. Some of the blocks have the same number on them, but for a game, every single block needs to have a special, unique number that no other block has.

First, the code lines up all the blocks in order from the smallest number to the biggest number so they are easy to look at. Then, it starts walking down the line to check each block one by one. It keeps a secret notebook to remember the smallest number that is allowed to be used next.

When the code looks at a block, it checks if that number is already too small to be unique. If the number is smaller than the next available spot, it adds a little bit to a total count to represent pushing that block up to a higher number. After that, it updates the notebook so the next block has to be at least one number higher than the one just looked at. The code keeps doing this until every block is happy with its own special number.

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