# LeetCode 945: Minimum Increment to Make Array Unique

## Problem Restatement

We are given an integer array:

```python
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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Minimum number of increment moves |
| Operation | Increase one element by `1` |
| Goal | All values become unique |
| Constraint | `1 <= nums.length <= 10^5` |
| Constraint | `0 <= nums[i] <= 10^5` |

Function shape:

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

## Examples

Example 1:

```python
nums = [1, 2, 2]
```

The value `2` appears twice.

Increment one of them:

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

This takes `1` move.

Answer:

```python
1
```

Example 2:

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

Sort it:

```python
[1, 1, 2, 2, 3, 7]
```

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

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

Moves:

```text
0 + 1 + 1 + 2 + 2 + 0 = 6
```

Answer:

```python
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:

```python
nums = [1, 1, 1, 1]
```

We need to turn it into:

```python
[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:

```python
prev
```

Then the current final value must be at least:

```python
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:

```python
moves = 0
prev = -1
```

For each number `x` in sorted order:

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

```python
new_value = max(x, prev + 1)
```

3. Add the increment amount:

```python
moves += new_value - x
```

4. Update:

```python
prev = new_value
```

Return `moves`.

## Walkthrough

Use:

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

Sort:

```python
[1, 1, 2, 2, 3, 7]
```

| Original `x` | Smallest allowed | Final value | Moves added |
|---:|---:|---:|---:|
| 1 | 0 | 1 | 0 |
| 1 | 2 | 2 | 1 |
| 2 | 3 | 3 | 1 |
| 2 | 4 | 4 | 2 |
| 3 | 5 | 5 | 2 |
| 7 | 6 | 7 | 0 |

Total moves:

```python
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:

```python
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:

```python
n = len(nums)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(1)` or `O(n)` | Depends on the sorting implementation |

The greedy scan after sorting is `O(n)`.

## Implementation

```python
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:

```python
nums.sort()
```

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

`prev` stores the previous final value:

```python
prev = -1
```

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

```python
new_value = max(x, prev + 1)
```

The number of moves for this element is:

```python
new_value - x
```

Then we update the previous final value:

```python
prev = new_value
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[1,2,2]` | Official basic case |
| `[3,2,1,2,1,7]` | Multiple duplicates |
| `[1,1,1,1]` | All values equal |
| `[0]` | Single element |
| `[0,0]` | Small duplicate case |
| `[0,2,2,2]` | Duplicate group with gap |
| `[5,5,5,5,5]` | Repeated same value |