563. Minimum Increment to Make Array Unique
You are given an array of integers nums. In one move you pick any element and add exactly 1 to it — you can never decrease a value.
Return the minimum total number of moves needed so that no two elements of nums end up equal.
The order of the array does not matter, only the final multiset of values, and values are allowed to grow past the original maximum.
Example 1:
Input: nums = [1, 2, 2]
Output: 1
Explanation: Bump one of the 2s up to 3. The array becomes [1, 2, 3] after a single move.
Example 2:
Input: nums = [3, 2, 1, 2, 1, 7]
Output: 6
Explanation: One optimal ending is [3, 4, 1, 2, 5, 7]: one 2 rises to 4 (2 moves) and one 1 rises all the way to 5 (4 moves) — 6 increments total, and no cheaper repair exists.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁵
Hints:
Order is irrelevant, so sort. After sorting, every clash is between neighbors — the second copy of a value has to move somewhere strictly above the element before it.
Sweep the sorted array while tracking the smallest value the current element is still allowed to take (one more than the previous element's final value). If the element is already above that floor it costs nothing; otherwise it costs floor − value moves.
Watch the total: with 10^5 equal elements the answer overflows 32-bit integers. Use a 64-bit accumulator in C++/Java.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 2]
Expected output: 1