945. Minimum Increment to Make Array Unique LeetCode Solution
In this guide, you will get 945. Minimum Increment to Make Array Unique LeetCode Solution with the best time and space complexity. The solution to Minimum Increment to Make Array Unique problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Increment to Make Array Unique
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.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].
Example 2:
Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown that it is impossible for the array to have all unique values with 5 or less moves.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})
945. Minimum Increment to Make Array Unique LeetCode Solution in C++
class Solution {
public:
int minIncrementForUnique(vector<int>& nums) {
int ans = 0;
int minAvailable = 0;
ranges::sort(nums);
for (const int num : nums) {
ans += max(minAvailable - num, 0);
minAvailable = max(minAvailable, num) + 1;
}
return ans;
}
}; /* code provided by PROGIEZ */
945. Minimum Increment to Make Array Unique LeetCode Solution in Java
class Solution {
public int minIncrementForUnique(int[] nums) {
int ans = 0;
int minAvailable = 0;
Arrays.sort(nums);
for (final int num : nums) {
ans += Math.max(minAvailable - num, 0);
minAvailable = Math.max(minAvailable, num) + 1;
}
return ans;
}
} // code provided by PROGIEZ
945. Minimum Increment to Make Array Unique LeetCode Solution in Python
class Solution:
def minIncrementForUnique(self, nums: list[int]) -> int:
ans = 0
minAvailable = 0
for num in sorted(nums):
ans += max(minAvailable - num, 0)
minAvailable = max(minAvailable, num) + 1
return ans # code by PROGIEZ
