Minimum Increment to Make Array Unique

Naive Approach (Brute Force)

One straightforward approach is to iterate through the array and, for each number, check if it already exists earlier in the array. If it does, increment the number until it becomes unique. This process continues until all numbers are unique.

Code (Python)

def min_moves_naive(nums):
    moves = 0
    for i in range(len(nums)):
        while nums[i] in nums[:i]:
            nums[i] += 1
            moves += 1
    return moves

Time Complexity: O(N^2) in the worst case

Space Complexity: O(1)

Optimal Approach (Sorting and Greedy)

To optimize, we can sort the array first. Then, we iterate through the sorted array, ensuring that each number is greater than the previous number by at least 1. If it's not, we increment it to be one greater than the previous, and we accumulate the moves.

Code (Python)

def min_moves(nums):
    nums.sort()
    moves = 0
    prev = 0
    for i in range(len(nums)):
        if i > 0:
            prev = nums[i-1]
        if nums[i] <= prev:
            moves += prev - nums[i] + 1
            nums[i] = prev + 1
    return moves

Time Complexity: O(N log N) due to sorting

Space Complexity: O(1) if sorting is done in-place, otherwise O(N)

Edge Cases

• Empty Array: If the input array is empty, the number of moves needed is 0.
• Already Unique: If the input array contains unique elements already, the number of moves needed is 0.
• Large Values: The problem states that the answer fits in a 32-bit integer, so we don't need to worry about integer overflow as long as we use standard integer types.
• Negative Values: The prompt says the values will be >= 0, so we don't need to consider negative values.

Explanation

The greedy approach works by ensuring that each element nums[i] is strictly greater than the element before it nums[i-1]. Sorting the array allows us to process elements in increasing order. If an element is less than or equal to the previous one, we increment it by the minimum amount to make it unique. This strategy minimizes the total number of moves because we are only ever incrementing when necessary to avoid duplicates and maintain uniqueness.