Problem Description
You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1. Return the minimum number of moves to make every value in nums unique.
Key Insights
- Duplicates in the array need to be resolved by incrementing values.
- The final unique values should be in a sorted sequence without gaps.
- Sorting the array helps to systematically resolve duplicates.
- The minimum increment needed to make values unique can be computed by comparing adjacent values after sorting.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - if sorting is done in place, otherwise O(n) for storing sorted results.
Solution
To solve the problem, we can use a greedy algorithm. First, we sort the array to group duplicates together. By iterating through the sorted array, we can check if the current number is less than or equal to the previous number. If it is, we need to increment it to be one more than the previous number, and we keep track of the total increments made. This approach ensures that we make the minimal number of moves to achieve uniqueness.