Minimum Increment to Make Array Unique

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. Your task is to find 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 <= 10^5
• 0 <= nums[i] <= 10^5

Minimum Increment to Make Array Unique

Problem Description

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. The objective is to determine the minimum number of moves required to make every value in nums unique.

Brute Force Solution

A brute-force approach involves iterating through the array and, for each element, checking if it is already present in the array. If a duplicate is found, increment the element until it becomes unique. The number of increments is counted to get the total number of moves.

def min_increment_for_unique_brute_force(nums):
    moves = 0
    seen = set()
    for i in range(len(nums)):
        while nums[i] in seen:
            nums[i] += 1
            moves += 1
        seen.add(nums[i])
    return moves

Optimal Solution

A more efficient solution involves sorting the array first. After sorting, iterate through the array, and if an element is less than or equal to the previous element, increment it until it is greater than the previous element. This guarantees that each element is unique while minimizing the number of moves.

def min_increment_for_unique(nums):
    nums.sort()
    moves = 0
    prev = -1
    for num in nums:
        if num <= prev:
            moves += prev - num + 1
            prev += 1
        else:
            prev = num
    return moves

Example

Consider the input nums = [3, 2, 1, 2, 1, 7]. Here's how the optimal solution works:

1. Sort the array: nums becomes [1, 1, 2, 2, 3, 7].
2. Initialize moves = 0 and prev = -1.
3. Iterate through the sorted array:
   • num = 1. Since 1 > -1, prev = 1.
   • num = 1. Since 1 <= 1, increment num to 2. moves += 1 - 1 + 1 = 1. prev = 2.
   • num = 2. Since 2 <= 2, increment num to 3. moves += 2 - 2 + 1 = 1. prev = 3.
   • num = 2. Since 2 <= 3, increment num to 4. moves += 3 - 2 + 1 = 2. prev = 4.
   • num = 3. Since 3 <= 4, increment num to 5. moves += 4 - 3 + 1 = 2. prev = 5.
   • num = 7. Since 7 > 5, prev = 7.
4. The total number of moves is 1 + 1 + 2 + 2 = 6.

Big(O) Run-time Analysis

The optimal solution has two main steps:

1. Sorting the array: This takes O(n log n) time, where n is the number of elements in the array.
2. Iterating through the sorted array: This takes O(n) time.

Therefore, the overall time complexity is O(n log n) + O(n) = O(n log n) because the sorting step dominates the iteration step.

Big(O) Space Usage Analysis

The optimal solution sorts the array in place, so it does not require any extra space proportional to the input size. Hence, the space complexity is O(1). If, however, the sorting algorithm used by nums.sort() requires extra space (e.g., merge sort), the space complexity could be O(n) in the worst case.

Edge Cases

1. Empty array: If the input array is empty, no moves are needed, and the function should return 0.
2. Array with one element: If the array has only one element, it is already unique, and the function should return 0.
3. Array with all identical elements: If all elements are the same, the algorithm will increment each element (except the first) to make them unique.

Code

def min_increment_for_unique(nums):
    nums.sort()
    moves = 0
    prev = -1
    for num in nums:
        if num <= prev:
            moves += prev - num + 1
            prev += 1
        else:
            prev = num
    return moves

# Example usage:
nums1 = [1, 2, 2]
print(f'Input: {nums1}, Output: {min_increment_for_unique(nums1)}')  # Output: 1

nums2 = [3, 2, 1, 2, 1, 7]
print(f'Input: {nums2}, Output: {min_increment_for_unique(nums2)}')  # Output: 6

nums3 = []
print(f'Input: {nums3}, Output: {min_increment_for_unique(nums3)}')  # Output: 0

nums4 = [5]
print(f'Input: {nums4}, Output: {min_increment_for_unique(nums4)}')  # Output: 0

nums5 = [4, 4, 4, 4]
print(f'Input: {nums5}, Output: {min_increment_for_unique(nums5)}')  # Output: 6