Minimum Increment to Make Array Unique
Problem
Return the minimum number of +1 moves so that all elements of nums are distinct.
nums = [3,2,1,2,1,7]6def minIncrementForUnique(nums):
nums.sort()
moves = 0
for i in range(1, len(nums)):
if nums[i] <= nums[i - 1]:
need = nums[i - 1] + 1
moves += need - nums[i]
nums[i] = need
return movesfunction minIncrementForUnique(nums) {
nums.sort((a, b) => a - b);
let moves = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] <= nums[i - 1]) {
const need = nums[i - 1] + 1;
moves += need - nums[i];
nums[i] = need;
}
}
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]) {
int need = nums[i - 1] + 1;
moves += need - nums[i];
nums[i] = need;
}
}
return moves;
}
}int minIncrementForUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
int moves = 0;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] <= nums[i - 1]) {
int need = nums[i - 1] + 1;
moves += need - nums[i];
nums[i] = need;
}
}
return moves;
}Explanation
We can only add +1 to values, so the cheapest way to remove a clash is to push a duplicate up to the smallest unused number just above its neighbor. Doing this in sorted order makes that neighbor obvious.
After sorting, we walk left to right. If nums[i] is not strictly greater than the value before it, it collides, so we lift it to need = nums[i-1] + 1 and add the cost need - nums[i] to moves.
This greedy choice is safe because we always bump to the lowest legal value, never wasting moves, and a sorted later element will simply be bumped above this new value if needed.
Example: [3,2,1,2,1,7] sorts to [1,1,2,2,3,7]. The second 1 becomes 2 (1 move), the first 2 stays but the later ones get pushed to 3, 4, 5.
Adding up all the lifts gives 6 total moves. Sorting plus a single left-to-right sweep is all it takes.