LeetCode 945: Minimum Increment to Make Array Unique

Problem Restatement

We are given an integer array:

nums

In one move, we may choose any index and increment that value by 1.

We need to return the minimum number of moves required to make every value in nums unique.

The problem guarantees that the answer fits in a 32-bit integer. The official examples include [1,2,2] -> 1 and [3,2,1,2,1,7] -> 6.

Input and Output

Function shape:

class Solution:
    def minIncrementForUnique(self, nums: list[int]) -> int:
        ...

Examples

Example 1:

nums = [1, 2, 2]

The value 2 appears twice.

Increment one of them:

[1, 2, 2] -> [1, 2, 3]

This takes 1 move.

Answer:

1

Example 2:

nums = [3, 2, 1, 2, 1, 7]

Sort it:

[1, 1, 2, 2, 3, 7]

Make each value at least one more than the previous value:

[1, 1, 2, 2, 3, 7]
[1, 2, 3, 4, 5, 7]

Moves:

0 + 1 + 1 + 2 + 2 + 0 = 6

Answer:

6

First Thought

A direct approach is to repeatedly find duplicates and increment one duplicate until it reaches an unused value.

This works, but it can do too much repeated searching.

For example:

nums = [1, 1, 1, 1]

We need to turn it into:

[1, 2, 3, 4]

If we handle duplicates one at a time without order, we may repeatedly check values that are already occupied.

Sorting makes the needed final values clear.

Key Insight

After sorting, we should process numbers from smallest to largest.

For each number, choose the smallest possible final value that keeps it unique.

Suppose the previous final value is:

prev

Then the current final value must be at least:

prev + 1

If the current number x is already larger than prev, we keep it.

If x <= prev, we increment it to prev + 1.

This greedy choice is optimal because assigning the current number to the smallest available valid value leaves as much room as possible for later numbers.

Algorithm

Sort nums.

Initialize:

moves = 0
prev = -1

For each number x in sorted order:

1. The smallest allowed final value is prev + 1.
2. Set:

new_value = max(x, prev + 1)

3. Add the increment amount:

moves += new_value - x

4. Update:

prev = new_value

Return moves.

Walkthrough

Use:

nums = [3, 2, 1, 2, 1, 7]

Sort:

[1, 1, 2, 2, 3, 7]

Total moves:

6

Correctness

After sorting, consider the numbers from smallest to largest.

For the first number, keeping it unchanged is always optimal because there is no earlier value to conflict with.

For every later number x, all previous final values are already fixed and unique. Let the largest previous final value be prev. To keep uniqueness while preserving sorted order, the current final value must be at least prev + 1.

The algorithm assigns:

max(x, prev + 1)

This is the smallest value that is both reachable by increments and unique relative to previous values.

Any valid solution must assign the current number to at least this value. Assigning it to anything larger would add extra moves and would not help previous numbers. It would also make later numbers no easier to place.

Therefore, the greedy choice is optimal for each sorted position.

By induction, after processing every number, the algorithm has built a unique array with the minimum total number of increments.

Complexity

Let:

n = len(nums)

The greedy scan after sorting is O(n).

Implementation

class Solution:
    def minIncrementForUnique(self, nums: list[int]) -> int:
        nums.sort()

        moves = 0
        prev = -1

        for x in nums:
            new_value = max(x, prev + 1)
            moves += new_value - x
            prev = new_value

        return moves

Code Explanation

Sort the array first:

nums.sort()

This groups duplicates and lets us assign final values from left to right.

prev stores the previous final value:

prev = -1

For each x, the final value must be at least prev + 1:

new_value = max(x, prev + 1)

The number of moves for this element is:

new_value - x

Then we update the previous final value:

prev = new_value

Testing

def run_tests():
    s = Solution()

    assert s.minIncrementForUnique([1, 2, 2]) == 1
    assert s.minIncrementForUnique([3, 2, 1, 2, 1, 7]) == 6

    assert s.minIncrementForUnique([1, 1, 1, 1]) == 6
    assert s.minIncrementForUnique([0]) == 0
    assert s.minIncrementForUnique([0, 0]) == 1
    assert s.minIncrementForUnique([0, 2, 2, 2]) == 3
    assert s.minIncrementForUnique([5, 5, 5, 5, 5]) == 10

    print("all tests passed")

run_tests()