Problem Description

You have an integer array nums. You can perform moves on this array where in each move, you select any index i (where 0 <= i < nums.length) and increase nums[i] by 1.

Your goal is to make all values in the array unique (no duplicate values). You need to find the minimum number of moves required to achieve this.

For example, if you have nums = [1, 2, 2], you would need to increment one of the 2s at least once to make it 3, resulting in [1, 2, 3] with all unique values. This would take 1 move.

The problem guarantees that the answer will fit in a 32-bit integer.

The key insight is that you can only increment values (never decrement), so you need to strategically choose which elements to increment and by how much to minimize the total number of operations while ensuring all final values are distinct.

Intuition

Since we can only increment values and not decrement them, the optimal strategy is to process numbers from smallest to largest. This way, we can ensure that each number is placed at the smallest possible unique position.

Think about it this way: if we have duplicate values or values that are too close together, we need to "push" some of them forward (increase them) to create gaps. By sorting the array first, we can process elements in order and maintain a running minimum value that each subsequent element must be at least equal to.

The key observation is that for each element in the sorted array, it should be at least one greater than the previous element to maintain uniqueness. If we track the minimum value y that the current element should become, we can calculate:

• If the current element x is already greater than y, we can keep it as is (set y = x)
• If the current element x is less than or equal to y, we must increment it to y + 1

For example, with sorted array [1, 1, 2, 2, 3]:

• First 1 stays as 1 (y becomes 1)
• Second 1 must become 2 (y becomes 2, we need 1 move)
• First 2 must become 3 (y becomes 3, we need 1 move)
• Second 2 must become 4 (y becomes 4, we need 2 moves)
• The 3 must become 5 (y becomes 5, we need 2 moves)

The formula y = max(y + 1, x) elegantly captures this logic: we either take the current element if it's already large enough, or we take the next available position y + 1.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a sorting + greedy approach:

1. Sort the array: First, we sort nums in ascending order. This allows us to process elements from smallest to largest, ensuring we can assign the minimum possible values to maintain uniqueness.

2. Initialize tracking variables:

   • ans = 0: Accumulates the total number of moves needed
   • y = -1: Tracks the minimum value the current element should become (initialized to -1 so the first element can be 0 if needed)

3. Iterate through sorted array: For each element x in the sorted array:

   • Calculate the minimum value this element should become: y = max(y + 1, x)
     • If x > y, then x is already large enough and doesn't conflict with previous elements, so y = x
     • If x <= y, then x needs to be incremented to at least y + 1 to maintain uniqueness
   • Add the number of moves needed: ans += y - x
     • This represents how many times we need to increment x to reach value y

4. Return the result: After processing all elements, ans contains the minimum total moves needed.

Example walkthrough with nums = [3, 2, 1, 2, 1, 7]:

• After sorting: [1, 1, 2, 2, 3, 7]
• Process 1: y = max(-1 + 1, 1) = 1, moves = 1 - 1 = 0
• Process 1: y = max(1 + 1, 1) = 2, moves = 2 - 1 = 1
• Process 2: y = max(2 + 1, 2) = 3, moves = 3 - 2 = 1
• Process 2: y = max(3 + 1, 2) = 4, moves = 4 - 2 = 2
• Process 3: y = max(4 + 1, 3) = 5, moves = 5 - 3 = 2
• Process 7: y = max(5 + 1, 7) = 7, moves = 7 - 7 = 0
• Total moves = 0 + 1 + 1 + 2 + 2 + 0 = 6

The time complexity is O(n log n) due to sorting, and the space complexity is O(1) if we don't count the sorting space.

Example Walkthrough

Let's walk through a small example with nums = [2, 2, 1] to illustrate the solution approach.

Step 1: Sort the array

• Original: [2, 2, 1]
• Sorted: [1, 2, 2]

Step 2: Initialize variables

• ans = 0 (total moves counter)
• y = -1 (tracks minimum value for current element)

Step 3: Process each element

Processing element 1 (index 0):

• Calculate: y = max(-1 + 1, 1) = max(0, 1) = 1
• This element stays at value 1
• Moves needed: 1 - 1 = 0
• Running total: ans = 0

Processing element 2 (index 1):

• Calculate: y = max(1 + 1, 2) = max(2, 2) = 2
• This element stays at value 2
• Moves needed: 2 - 2 = 0
• Running total: ans = 0

Processing element 2 (index 2):

• Calculate: y = max(2 + 1, 2) = max(3, 2) = 3
• This element must be incremented to 3 (since 2 is already taken)
• Moves needed: 3 - 2 = 1
• Running total: ans = 1

Step 4: Result

• Final array values would be: [1, 2, 3] (all unique)
• Minimum moves required: 1

The algorithm ensures each element gets the smallest possible unique value by processing them in sorted order and tracking the minimum available position with variable y.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(n log n), where n is the length of the array nums. This is dominated by the sorting operation nums.sort(), which takes O(n log n) time. The subsequent for loop iterates through the sorted array once, performing constant-time operations (max, addition, subtraction) in each iteration, contributing O(n) time. Since O(n log n) + O(n) = O(n log n), the overall time complexity is O(n log n).

The space complexity is O(log n). While the algorithm only uses a constant amount of extra variables (ans and y), the sorting operation typically requires O(log n) space for the recursion stack when using algorithms like quicksort or the temporary space used in merge sort's divide-and-conquer approach. Python's built-in sort() method uses Timsort, which has a worst-case space complexity of O(n), but typically uses O(log n) space in practice. Following the reference answer's assessment, the space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Track Used Values with a Set/HashSet

A common mistake is trying to solve this problem by maintaining a set of already-used values and incrementing duplicates until they find an unused slot:

Incorrect Approach:

def minIncrementForUnique(self, nums: List[int]) -> int:
    used = set()
    total_moves = 0
  
    for num in nums:
        current = num
        while current in used:
            current += 1
            total_moves += 1
        used.add(current)
  
    return total_moves

Why it fails: This approach has terrible time complexity. In the worst case (e.g., nums = [1, 1, 1, ..., 1] with n elements), each subsequent element needs to search through increasingly large ranges, leading to O(n²) time complexity or worse.

Solution: Always sort first! The sorted + greedy approach ensures O(n log n) time complexity and avoids redundant searching.

2. Not Handling the Case Where Original Values Are Already Larger

Some implementations forget that if a number is already larger than the minimum required value, we should use it as-is:

Incorrect:

def minIncrementForUnique(self, nums: List[int]) -> int:
    nums.sort()
    total_moves = 0
  
    for i in range(1, len(nums)):
        if nums[i] <= nums[i-1]:
            target = nums[i-1] + 1
            total_moves += target - nums[i]
            nums[i] = target  # Modifying the array
  
    return total_moves

Problem: This only handles consecutive duplicates but misses the optimization when numbers have gaps. Also, it modifies the input array unnecessarily.

Solution: Use max(next_available + 1, current_num) to handle both cases elegantly without modifying the input.

3. Integer Overflow Concerns (Language-Specific)

In languages like Java or C++, calculating the sum of moves might overflow:

Potential Issue:

int totalMoves = 0;  // Using int in Java
for (int num : nums) {
    // Large differences could cause overflow
    totalMoves += nextAvailable - num;
}

Solution: Use appropriate data types (long in Java, long long in C++) even though the problem states the answer fits in 32-bit integer. The intermediate calculations might still overflow before the final result.

4. Off-by-One Error in Initial Value

Starting with the wrong initial value for tracking the next available position:

Incorrect:

next_available = 0  # Wrong initialization

Problem: This forces the first element to be at least 0, which might require unnecessary moves if the first element is negative.

Solution: Initialize to a value that ensures the first element can keep its original value if possible (like -1 or float('-inf')).