Sponsored
This approach involves sorting the array first, and then iterating through it to ensure each element is greater than the previous. By keeping track of the necessary increments for each duplicate, we can ensure that every element in the array becomes unique.
Time Complexity: O(N log N) due to sorting and O(N) for linear traversal, resulting in O(N log N) overall.
Space Complexity: O(1) since no auxiliary space is used beyond input manipulation.
1def min_increment_for_unique(nums):
2 nums.sort()
3 moves, need = 0, nums[0]
4 for num in nums:
5 moves += max(0, need - num)
6 need = max(need, num) + 1
7 return moves
8
9nums = [3,2,1,2,1,7]
10print(min_increment_for_unique(nums))This Python solution sorts the input list and processes each element to determine the number of moves required to achieve a unique array. It leverages the sorted order to ensure minimal increments.
Instead of sorting, this method uses an array to count occurrences of each integer and then processes the count. For duplicate values, increments are calculated to fill gaps until all numbers are unique.
Time Complexity: O(N + M) where M is the range of numbers, due to counting and traversal.
Space Complexity: O(M) where M is the maximum possible number in nums.
1
We count the occurrences of each number in the array using a fixed-size count array. Excess occurrences (duplicates) are queued for repositioning to the next available slot found.