medium Minimum Increment to Make Array Unique

Problem Statement

You are given an array of integers nums. In a single move, you can pick any index i, where 0 <= i < nums.length and add 1 to nums[i].

Return the minimum number of moves to make all elements in the nums unique.

Examples

Example 1

• Input: nums = [4, 3, 2, 2, 1, 4]
• Output: 5
• Explanation: We need 1 move to increment the 4 at index 5 to 5, and then 4 moves to increment the 2 at index 4 to 6. So, we need total 5 moves.

Example 2

• Input: nums = [5, 5, 5, 5, 5]
• Output: 10
• Explanation: Increment each subsequent 5 to get [5, 6, 7, 8, 9], needing 10 moves.

Example 3

• Input: nums = [1, 1, 1, 1, 2]
• Output: 9
• Explanation: Increment three of the 1s to get [1, 2, 3, 4, 2] with 1 + 2 + 3 = 6 moves, then increment the second 2 to 5 to get [1, 2, 3, 4, 5] with 3 moves, needing total 9 moves.

Constraints:

• 1 <= nums.length <= 10⁵
• 0 <= nums[i] <= 10⁵

Solution

To solve this problem, we use a counting approach instead of sorting to maintain efficiency. First, we find the maximum value in the array to determine the range for our frequency counting array. Then, we populate this array with the frequency of each value in the input array. By iterating over the frequency count array, we ensure each value is unique by carrying over excess counts to the next value. This approach avoids the overhead of sorting and efficiently handles the uniqueness requirement.

The counting approach is effective because it directly addresses the issue of duplicate values and provides a straightforward way to ensure uniqueness with minimal operations. By keeping track of the frequency of each value and adjusting accordingly, we can achieve the desired result efficiently.

Step-by-step Algorithm

1. Find the maximum value in the array:

   • Iterate through the array nums to determine the highest value. This will help us define the range of our frequency array.

2. Create a frequency count array:

   • Initialize an array frequency with a size of n + max, where n is the length of nums and max is the highest value found in step 1.

3. Populate the frequency count array:

   • Iterate through nums and for each value val, increment frequency[val] by 1.

4. Adjust frequencies to make all values unique:

   • Iterate over the frequency array.
   • For each index i in frequency:
     • If frequency[i] is less than or equal to 1, continue to the next index. It means no more moves are needed from the current index i.
     • Otherwise, calculate the excess occurrences as frequency[i] - 1.
     • Add these excess occurrences to frequency[i + 1]. (Moving all excess elements to the next index).
     • Add the excess occurrences to minMoves (to keep track of the total increments needed).

5. Return the total number of moves:

   • The variable minMoves now contains the minimum number of increments required to make all values in nums unique.

Algorithm Walkthrough

Let's walk through the algorithm using the input [4, 3, 2, 2, 1, 4].

1. Find the maximum value in the array:

   • Iterate through nums: [4, 3, 2, 2, 1, 4]
   • Maximum value is 4.

2. Create a frequency count array:

   • Initialize frequency array of size 6 + 4 = 10 (size of nums plus max value).
   • Frequency array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

3. Populate the frequency count array:

   • For nums[0] = 4: Increment frequency[4] by 1 → [0, 0, 0, 0, 1, 0, 0, 0, 0, 0].
   • For nums[1] = 3: Increment frequency[3] by 1 → [0, 0, 0, 1, 1, 0, 0, 0, 0, 0].
   • For nums[2] = 2: Increment frequency[2] by 1 → [0, 0, 1, 1, 1, 0, 0, 0, 0, 0].
   • For nums[3] = 2: Increment frequency[2] by 1 → [0, 0, 2, 1, 1, 0, 0, 0, 0, 0].
   • For nums[4] = 1: Increment frequency[1] by 1 → [0, 1, 2, 1, 1, 0, 0, 0, 0, 0].
   • For nums[5] = 4: Increment frequency[4] by 1 → [0, 1, 2, 1, 2, 0, 0, 0, 0, 0].

4. Adjust frequencies to make all values unique:

   • Initialize minMoves to 0.
   • For i = 0: frequency[0] is 0 → continue.
   • For i = 1: frequency[1] is 1 → continue.
   • For i = 2: frequency[2] is 2.
     • Calculate excess as 2 - 1 = 1.
     • Increment frequency[3] by 1 → [0, 1, 2, 2, 2, 0, 0, 0, 0, 0].
     • Increment minMoves by 1 → minMoves = 1.
   • For i = 3: frequency[3] is 2.
     • Calculate excess as 2 - 1 = 1.
     • Increment frequency[4] by 1 → [0, 1, 2, 2, 3, 0, 0, 0, 0, 0].
     • Increment minMoves by 1 → minMoves = 2.
   • For i = 4: frequency[4] is 3.
     • Calculate excess as 3 - 1 = 2.
     • Increment frequency[5] by 2 → [0, 1, 2, 2, 3, 2, 0, 0, 0, 0].
     • Increment minMoves by 2 → minMoves = 4.
   • For i = 5: frequency[5] is 2.

     • Calculate excess as 2 - 1 = 1.

     • Increment frequency[6] by 1 → [0, 1, 2, 2, 3, 2, 1, 0, 0, 0].

     • Increment minMoves by 1 → minMoves = 5.

5. Return the total number of moves:

   • The minimum number of moves required is 5.

Code

class Solution {

  public int minIncrementForUnique(int[] nums) {
    int n = nums.length;
    int max = 0;
    int minMoves = 0;

    // Find the maximum value in the array
    for (int value : nums) {
      max = Math.max(max, value);
    }

    // Create a frequency array to count occurrences
    int[] frequency = new int[n + max];

    // Populate the frequency array
    for (int value : nums) {
      frequency[value]++;
    }

    // Adjust frequencies to make all values unique
    for (int i = 0; i < frequency.length; i++) {
      if (frequency[i] <= 1) continue; // Skip if frequency is 1 or less

      int excess = frequency[i] - 1; // Calculate excess duplicates
      frequency[i + 1] += excess; // Move excess to the next value
      minMoves += excess; // Count moves required
    }

    return minMoves; // Return total moves
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(
      solution.minIncrementForUnique(new int[] { 4, 3, 2, 2, 1, 4 })
    ); // Output: 5
    System.out.println(
      solution.minIncrementForUnique(new int[] { 5, 5, 5, 5, 5 })
    ); // Output: 10
    System.out.println(
      solution.minIncrementForUnique(new int[] { 1, 1, 1, 1, 2 })
    ); // Output: 9
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm can be broken down into the following steps:

1. Finding the maximum value in the array:
2. Populating the frequency array:
3. Iterating over the frequency array to adjust the counts: , where max is the maximum value in the array.

Overall, the time complexity is .

Space Complexity

The space complexity is determined by the size of the frequency array, which is n + max. Hence, the space complexity is .