0% completed
Problem Statement
You are given an array of integers nums
. In a single move, you can pick any index i
, where 0 <= i < nums.length
and add 1
to nums[i]
.
Return the minimum number of moves to make all elements in the nums
unique
.
Examples
Example 1
- Input: nums =
[4, 3, 2, 2, 1, 4]
- Output:
5
- Explanation: We need
1
move to increment the4
at index 5 to5
, and then4
moves to increment the2
at index 4 to6
. So, we need total5
moves.
Example 2
- Input: nums =
[5, 5, 5, 5, 5]
- Output:
10
- Explanation: Increment each subsequent
5
to get [5, 6, 7, 8, 9], needing10
moves.
Example 3
- Input: nums =
[1, 1, 1, 1, 2]
- Output:
9
- Explanation: Increment three of the 1s to get [1, 2, 3, 4, 2] with
1 + 2 + 3 = 6
moves, then increment the second2
to5
to get [1, 2, 3, 4, 5] with3
moves, needing total9
moves.
Constraints:
- 1 <= nums.length <= 10<sup>5</sup>
- 0 <= nums[i] <= 10<sup>5</sup>
Solution
To solve this problem, we use a counting approach instead of sorting to maintain efficiency. First, we find the maximum value in the array to determine the range for our frequency counting array. Then, we populate this array with the frequency of each value in the input array. By iterating over the frequency count array, we ensure each value is unique by carrying over excess counts to the next value. This approach avoids the overhead of sorting and efficiently handles the uniqueness requirement.
The counting approach is effective because it directly addresses the issue of duplicate values and provides a straightforward way to ensure uniqueness with minimal operations. By keeping track of the frequency of each value and adjusting accordingly, we can achieve the desired result efficiently.
Step-by-step Algorithm
-
Find the maximum value in the array:
- Iterate through the array nums to determine the highest value. This will help us define the range of our frequency array.
-
Create a frequency count array:
- Initialize an array frequency with a size of
n + max
, wheren
is the length of nums and max is the highest value found in step 1.
- Initialize an array frequency with a size of
-
Populate the frequency count array:
- Iterate through nums and for each value val, increment frequency[val] by 1.
-
Adjust frequencies to make all values unique:
- Iterate over the frequency array.
- For each index i in frequency:
- If frequency[i] is less than or equal to 1, continue to the next index. It means no more moves are needed from the current index
i
. - Otherwise, calculate the excess occurrences as
frequency[i] - 1
. - Add these excess occurrences to
frequency[i + 1]
. (Moving all excess elements to the next index). - Add the excess occurrences to minMoves (to keep track of the total increments needed).
- If frequency[i] is less than or equal to 1, continue to the next index. It means no more moves are needed from the current index
-
Return the total number of moves:
- The variable minMoves now contains the minimum number of increments required to make all values in nums unique.
Algorithm Walkthrough
Let's walk through the algorithm using the input [4, 3, 2, 2, 1, 4]
.
-
Find the maximum value in the array:
- Iterate through nums: [4, 3, 2, 2, 1, 4]
- Maximum value is 4.
-
Create a frequency count array:
- Initialize frequency array of size
6 + 4 = 10
(size of nums plus max value). - Frequency array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
.
- Initialize frequency array of size
-
Populate the frequency count array:
- For nums[0] = 4: Increment
frequency[4]
by 1 →[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
. - For nums[1] = 3: Increment
frequency[3]
by 1 →[0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
. - For nums[2] = 2: Increment
frequency[2]
by 1 →[0, 0, 1, 1, 1, 0, 0, 0, 0, 0]
. - For nums[3] = 2: Increment
frequency[2]
by 1 →[0, 0, 2, 1, 1, 0, 0, 0, 0, 0]
. - For nums[4] = 1: Increment
frequency[1]
by 1 →[0, 1, 2, 1, 1, 0, 0, 0, 0, 0]
. - For nums[5] = 4: Increment
frequency[4]
by 1 →[0, 1, 2, 1, 2, 0, 0, 0, 0, 0]
.
- For nums[0] = 4: Increment
-
Adjust frequencies to make all values unique:
- Initialize minMoves to 0.
- For i = 0:
frequency[0]
is 0 → continue. - For i = 1:
frequency[1]
is 1 → continue. - For i = 2:
frequency[2]
is 2.- Calculate excess as
2 - 1 = 1
. - Increment
frequency[3]
by 1 →[0, 1, 2, 2, 2, 0, 0, 0, 0, 0]
. - Increment minMoves by 1 →
minMoves = 1
.
- Calculate excess as
- For i = 3:
frequency[3]
is 2.- Calculate excess as
2 - 1 = 1
. - Increment
frequency[4]
by 1 →[0, 1, 2, 2, 3, 0, 0, 0, 0, 0]
. - Increment minMoves by 1 →
minMoves = 2
.
- Calculate excess as
- For i = 4:
frequency[4]
is 3.- Calculate excess as
3 - 1 = 2
. - Increment
frequency[5]
by 2 →[0, 1, 2, 2, 3, 2, 0, 0, 0, 0]
. - Increment minMoves by 2 →
minMoves = 4
.
- Calculate excess as
- For i = 5:
frequency[5]
is 2.-
Calculate excess as
2 - 1 = 1
. -
Increment
frequency[6]
by 1 →[0, 1, 2, 2, 3, 2, 1, 0, 0, 0]
. -
Increment minMoves by 1 →
minMoves = 5
.
-
-
Return the total number of moves:
- The minimum number of moves required is 5.
Code
Complexity Analysis
Time Complexity
The time complexity of the algorithm can be broken down into the following steps:
- Finding the maximum value in the array: O(n)
- Populating the frequency array: O(n)
- Iterating over the frequency array to adjust the counts: O(n + max), where max is the maximum value in the array.
Overall, the time complexity is O(n + max).
Space Complexity
The space complexity is determined by the size of the frequency array, which is n + max
. Hence, the space complexity is O(n + max).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible