# Minimum Increment to Make Array Unique
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-increment-to-make-array-unique)
Canonical: https://scaleengineer.com/dsa/problems/minimum-increment-to-make-array-unique
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [ZScaler](https://scaleengineer.com/companies/zscaler), [Coursera](https://scaleengineer.com/companies/coursera)
---
## Problem
You are given an integer array `nums`. In one move, you can pick an index `i` where `0 <= i < nums.length` and increment `nums[i]` by `1`.

Return _the minimum number of moves to make every value in_ `nums` _**unique**_.

The test cases are generated so that the answer fits in a 32-bit integer.

**Example 1:**

**Input:** nums = [1,2,2]
**Output:** 1
**Explanation:** After 1 move, the array could be [1, 2, 3].

**Example 2:**

**Input:** nums = [3,2,1,2,1,7]
**Output:** 6
**Explanation:** After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown that it is impossible for the array to have all unique values with 5 or less moves.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Brute-Force with Hashing
This approach iterates through each number in the input array and uses a hash set to keep track of the numbers that have already been used. For each number, if it's already in the set, we increment the number (and a move counter) repeatedly until we find a value that is not yet in the set. Then, we add this new unique value to the set and proceed to the next number in the input array.
**Time:** O(N + M), where N is the length of `nums` and M is the total number of increments. In the worst-case scenario (e.g., an array of all zeros), M can be on the order of O(N^2), making the overall time complexity effectively O(N^2). · **Space:** O(N), where N is the number of elements in `nums`. In the worst case, all numbers become unique and are stored in the `HashSet`.
**Pros:** Simple to understand and implement.; Does not require modifying the input array.
**Cons:** Highly inefficient for inputs with many duplicates or large values, as the inner `while` loop can execute many times.; Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits for the given constraints.
### Explanation
The brute-force method directly simulates the process of making numbers unique. We process the array element by element. For each element, we check if we have seen it before using a `HashSet` for efficient O(1) average time lookups. If we have seen the number, we are forced to increment it. We continue incrementing, adding 1 to our total moves count for each increment, until we find a number that has not been seen before. We then add this newly found unique number to our set of seen numbers and move on. While simple, this can be very slow if many increments are needed for a single element.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        int moves = 0;
        for (int num : nums) {
            while (seen.contains(num)) {
                num++;
                moves++;
            }
            seen.add(num);
        }
        return moves;
    }
}
```
### Algorithm
*   Initialize `moves = 0`.
*   Initialize an empty `HashSet<Integer> seen` to store unique numbers encountered so far.
*   Iterate through each number `num` in the input array `nums`.
*   For each `num`, enter a loop that continues as long as `num` is already in the `seen` set.
*   Inside the `while` loop, increment `num` by 1 and also increment the `moves` counter. This finds the next available unique integer.
*   Once the loop terminates, `num` holds a value not present in `seen`. Add this new unique `num` to the `seen` set.
*   After iterating through all the elements of `nums`, return the total `moves`.

## Sorting and Greedy Increment
This approach is based on a greedy strategy. By sorting the array first, we can process the numbers in increasing order. This allows us to make a locally optimal choice at each step that leads to a globally optimal solution. For any number that is not greater than the previous number in the sorted array, we increment it just enough to be one greater than the previous one. This is the minimum possible increment to resolve the conflict, thus minimizing the total moves.
**Time:** O(N log N), dominated by the initial sorting step. The subsequent linear scan of the array takes O(N) time. · **Space:** O(log N) or O(N), depending on the space complexity of the sorting algorithm used. Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
**Pros:** Guaranteed to find the minimum number of moves.; Significantly more efficient than the brute-force approach.; Relatively easy to reason about after sorting.
**Cons:** The O(N log N) time complexity from sorting is not the fastest possible solution.; This approach modifies the input array. A copy should be made if the original array needs to be preserved.
### Explanation
The core idea is that after sorting, each element `nums[i]` must be at least `nums[i-1] + 1` to be unique. If we find an element `nums[i]` that is less than or equal to `nums[i-1]`, we must increment it. The minimum number of moves to make `nums[i]` unique is to change it to `nums[i-1] + 1`. We add the difference `(nums[i-1] + 1) - nums[i]` to our total moves and update `nums[i]` to this new value. This update is crucial because the next element `nums[i+1]` will be compared against this new, larger value of `nums[i]`. This greedy choice works because we've sorted the array, so we only need to ensure an element is larger than its immediate predecessor.

```java
import java.util.Arrays;

class Solution {
    public int minIncrementForUnique(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int moves = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[i-1]) {
                int increment = nums[i-1] - nums[i] + 1;
                moves += increment;
                nums[i] = nums[i-1] + 1;
            }
        }
        return moves;
    }
}
```
### Algorithm
*   Sort the input array `nums` in non-decreasing order.
*   Initialize `moves = 0`.
*   Iterate through the sorted array from the second element (index `i = 1`) to the end.
*   At each element `nums[i]`, compare it with the previous element `nums[i-1]`.
*   If `nums[i] <= nums[i-1]`, it means `nums[i]` is not unique. The smallest unique value it can take is `nums[i-1] + 1`.
*   Calculate the required increment: `increment = nums[i-1] - nums[i] + 1`.
*   Add this `increment` to the total `moves`.
*   Update the current element's value to its new unique value: `nums[i] = nums[i-1] + 1`. This ensures the correct baseline for the next element.
*   If `nums[i] > nums[i-1]`, the element is already unique with respect to the previous ones, so no action is needed.
*   Return `moves` after the loop.

## Counting with Carry-over
This approach leverages the fact that the values in the array are within a manageable range. We can use a frequency array (a form of counting sort) to count the occurrences of each number. Then, we iterate through the numbers from 0 upwards. If we find a number with more than one occurrence, we know we have duplicates. We keep one and 'carry over' the extras to the next integer, adding the number of carried-over duplicates to our total moves. This is because each carried-over duplicate must be incremented at least once to move to the next integer slot.
**Time:** O(N + K), where N is `nums.length` and K is the maximum value in `nums`. We make one pass to populate the counts (O(N)) and one pass over the counts array (O(N+K)). This is linear time. · **Space:** O(N + K), where N is `nums.length` and K is the maximum value in `nums`. This is for the frequency array.
**Pros:** Achieves linear time complexity, making it the most efficient solution for the given constraints.; Avoids the O(N log N) overhead of sorting.
**Cons:** Requires a large amount of auxiliary space, proportional to the maximum value in the array plus its length. This can be a problem if the number range is very large.
### Explanation
This method avoids sorting by directly counting the numbers. We create an array, `counts`, large enough to hold the frequency of all numbers in the input, plus any new numbers we might generate. The maximum possible number could be `max_val + N`. After counting the initial frequencies, we iterate through the `counts` array. At any index `i`, if `counts[i]` is greater than 1, we have `counts[i] - 1` duplicates. Each of these must be incremented. We add `counts[i] - 1` to our total moves and pass these duplicates on to the next index by adding `counts[i] - 1` to `counts[i+1]`. This efficiently processes all duplicates by moving them up to the next available slots in a single pass.

```java
class Solution {
    public int minIncrementForUnique(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        
        // The size needs to accommodate the max original value plus potential increments.
        // maxVal + nums.length is a safe upper bound.
        int[] counts = new int[maxVal + nums.length + 1];
        for (int num : nums) {
            counts[num]++;
        }
        
        int moves = 0;
        for (int i = 0; i < counts.length - 1; i++) {
            if (counts[i] <= 1) {
                continue;
            }
            
            int duplicates = counts[i] - 1;
            moves += duplicates;
            counts[i+1] += duplicates;
        }
        
        return moves;
    }
}
```
### Algorithm
*   Determine the required size for a frequency array. This will be `max(nums) + nums.length` to accommodate all original numbers and potential increments.
*   Create a frequency array `counts` of this size, initialized to zeros.
*   Iterate through the input `nums` and populate the frequency array: for each `num`, increment `counts[num]`.
*   Initialize `moves = 0`.
*   Iterate through the `counts` array from index `i = 0` up to its end.
*   If `counts[i] > 1`, it means there are duplicates of the number `i`.
*   The number of duplicates to be moved is `duplicates = counts[i] - 1`.
*   These duplicates must be incremented to at least `i + 1`. Add `duplicates` to the total `moves`.
*   Carry over these duplicates to the next number's count: `counts[i+1] += duplicates`.
*   After the loop, return the total `moves`.

# Solutions
### Java

```java
class Solution {
public
  int minIncrementForUnique(int[] nums) {
    Arrays.sort(nums);
    int ans = 0;
    for (int i = 1; i < nums.length; ++i) {
      if (nums[i] <= nums[i - 1]) {
        int d = nums[i - 1] - nums[i] + 1;
        nums[i] += d;
        ans += d;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int: nums . sort() ans = 0 for i in range(1, len(nums)): if nums[i] <= nums[i - 1]: d = nums[i - 1] - nums[i] + 1 nums[i] += d ans += d return ans

```

### CPP

```cpp
class Solution {
public:
  int minIncrementForUnique(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int ans = 0;
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] <= nums[i - 1]) {
        int d = nums[i - 1] - nums[i] + 1;
        nums[i] += d;
        ans += d;
      }
    }
    return ans;
  }
};

```