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 <= 1050 <= nums[i] <= 105The goal of #945 Minimum Increment to Make Array Unique is to transform an integer array so that every element becomes unique using the minimum number of increments. Since you can only increase values, the challenge is to resolve duplicates efficiently while keeping the total increments as small as possible.
A common strategy is to sort the array first. After sorting, iterate through the elements and ensure that each number is at least one greater than the previous number. If the current value is less than or equal to the previous value, increment it to the smallest valid value and add the difference to the total cost. This forms a greedy approach where each step locally ensures uniqueness with minimal increments.
Another idea uses a counting / frequency approach to track duplicates and push extra occurrences forward to the next available numbers. Both strategies rely on maintaining the smallest valid unique value while processing the array. The sorting-based solution typically runs in O(n log n) time with O(1) or O(n) extra space depending on implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Greedy Adjustment | O(n log n) | O(1) or O(n) |
| Counting / Frequency Propagation | O(n + k) | O(n + k) |
NeetCodeIO
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
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
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting places duplicate or smaller elements next to each other, making it easy to enforce a strictly increasing order. This allows the algorithm to greedily adjust only the values that violate uniqueness, minimizing unnecessary increments.
Yes, problems involving greedy logic, duplicate handling, and array manipulation are common in technical interviews at large tech companies. This problem tests your ability to combine sorting with a greedy strategy and analyze time complexity.
The most common optimal approach is to sort the array and use a greedy strategy. After sorting, ensure each element is at least one greater than the previous element, incrementing when necessary. This minimizes the number of increments while keeping the algorithm efficient.
Arrays combined with sorting are typically sufficient for this problem. In some implementations, a frequency array or hash-based counting structure can help track duplicates and move extra values forward efficiently.
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.