Code Implementation

class Solution:
    def minIncrementForUnique(self, nums):
        nums.sort()
        moves = 0
        for i in range(1, len(nums)):
            if nums[i] <= nums[i-1]:
                increment = nums[i-1] + 1 - nums[i]
                nums[i] = nums[i-1] + 1
                moves += increment
        return moves
      

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

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

var minIncrementForUnique = function(nums) {
    nums.sort((a, b) => a - b);
    let moves = 0;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] <= nums[i - 1]) {
            moves += nums[i - 1] + 1 - nums[i];
            nums[i] = nums[i - 1] + 1;
        }
    }
    return moves;
};
      

Problem Description

Given an array of integers nums, you are allowed to increment any element by 1 any number of times. Your goal is to make every value in nums unique, using the minimum total number of increments across all elements.

Return the minimum number of increments needed to make the array unique. Each increment operation increases an element by exactly 1, and no two elements can have the same value after all operations are performed.

• Input: nums (array of integers, possibly with duplicates)
• Output: Integer (minimum number of increments required)
• Constraints: There is always at least one valid solution. Do not reuse elements; all values in the final array must be unique.

Thought Process

At first glance, it seems we could simply check for duplicates and increment them until they're unique. However, this can become inefficient if there are many duplicates or large gaps between numbers.

A naive brute-force approach would be, for every element, to check if it's already present in the array and increment it until it becomes unique. But this is slow, especially for large arrays, because each check and increment can take a lot of time.

Instead, we can optimize by sorting the array first. This way, duplicates or numbers that would cause conflicts are adjacent, making it much easier to identify and resolve collisions in one pass. By always comparing each number to its immediate predecessor, we can efficiently determine whether an increment is needed.

The key realization is that, after sorting, if nums[i] is less than or equal to nums[i-1], we must increment nums[i] to be one greater than nums[i-1] to maintain uniqueness.

Solution Approach

• Step 1: Sort the Array
  • Sorting arranges all duplicates and potential conflicts next to each other.
• Step 2: Iterate and Adjust
  • Start from the second element (index 1).
  • For each element, compare it to the previous one.
  • If the current value is less than or equal to the previous value, increment it to be exactly one more than the previous value.
  • Keep track of the total number of increments performed.
• Step 3: Return the Result
  • After processing the entire array, return the total increments needed.

This approach is efficient because sorting is O(n log n) and the single pass is O(n). No extra data structures are needed beyond the input array.

Example Walkthrough

Let's consider the input nums = [3, 2, 1, 2, 1, 7].

1. Sort the array: [1, 1, 2, 2, 3, 7]
2. Process each element:
   • i=1: nums[1]=1, nums[0]=1. Since 1 ≤ 1, increment to 2. Moves: 1. Array: [1, 2, 2, 2, 3, 7]
   • i=2: nums[2]=2, nums[1]=2. Since 2 ≤ 2, increment to 3. Moves: 2. Array: [1, 2, 3, 2, 3, 7]
   • i=3: nums[3]=2, nums[2]=3. Since 2 ≤ 3, increment to 4. Moves: 4. Array: [1, 2, 3, 4, 3, 7]
   • i=4: nums[4]=3, nums[3]=4. Since 3 ≤ 4, increment to 5. Moves: 6. Array: [1, 2, 3, 4, 5, 7]
   • i=5: nums[5]=7, nums[4]=5. Since 7 > 5, no increment needed. Moves: 6.
3. Total moves: 6
4. Final array: [1, 2, 3, 4, 5, 7] (all unique!)

Time and Space Complexity

• Brute-force approach:
  • For each duplicate, repeatedly check and increment until unique.
  • Worst-case time: O(n^2) (lots of repeated checks/increments).
  • Space: O(1) extra, but inefficient in time.
• Optimized approach:
  • Sorting: O(n log n)
  • Single pass: O(n)
  • Total Time: O(n log n)
  • Space: O(1) (if sorting in-place), otherwise O(n) if a copy is made.

The optimized method is much faster for large arrays because it avoids repeated scanning and uses sorting to cluster duplicates.

Summary

To make an array unique with the minimum number of increments, sort the array and then increment any value that is less than or equal to its predecessor. This ensures each value is unique with the least effort. The key insight is that sorting makes it easy to identify and fix conflicts in one efficient pass, leading to a simple and elegant O(n log n) solution.