LeetCode 945: Minimum Increment to Make Array Unique

Explanation:

To make every value in the array unique, we can iterate through the array and keep track of the current maximum value encountered so far. For each element in the array, if it is less than or equal to the current maximum value, we need to increment it to be greater than the current maximum value. The minimum number of moves required is equal to the total number of increments made.

Algorithm:

1. Sort the array nums.
2. Initialize a variable moves to 0 and maxVal to -1.
3. Iterate through the sorted array:
   • If the current element is less than or equal to maxVal, increment it to be maxVal + 1 and add the difference to moves.
   • Update maxVal to be the maximum of the current element and maxVal.
4. Return moves.

Time Complexity: O(nlogn) - Sorting the array Space Complexity: O(1) - Constant space is used

:

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