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] <= 105This 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.
First, we sort the array. We then iterate over the sorted array while tracking the next needed number to ensure uniqueness. For each element, we calculate the necessary moves by comparing it to the needed value, increment the moves counter accordingly, and then determine what the next needed unique value would be.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Sorting and Linear Scan | Time Complexity: O(N log N) due to sorting and O(N) for linear traversal, resulting in O(N log N) overall. |
| Use Count Array | Time Complexity: O(N + M) where M is the range of numbers, due to counting and traversal. |
Minimum Increment to Make Array Unique - Leetcode 945 - Python • NeetCodeIO • 15,643 views views
Watch 9 more video solutions →Practice Minimum Increment to Make Array Unique with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor