Minimum Increment to Make Array Unique
MedPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each number in the input array and uses a hash set to keep track of the numbers that have already been used. For each number, if it's already in the set, we increment the number (and a move counter) repeatedly until we find a value that is not yet in the set. Then, we add this new unique value to the set and proceed to the next number in the input array.
Algorithm
- Initialize
moves = 0. - Initialize an empty
HashSet<Integer> seento store unique numbers encountered so far. - Iterate through each number
numin the input arraynums. - For each
num, enter a loop that continues as long asnumis already in theseenset. - Inside the
whileloop, incrementnumby 1 and also increment themovescounter. This finds the next available unique integer. - Once the loop terminates,
numholds a value not present inseen. Add this new uniquenumto theseenset. - After iterating through all the elements of
nums, return the totalmoves.
Walkthrough
The brute-force method directly simulates the process of making numbers unique. We process the array element by element. For each element, we check if we have seen it before using a HashSet for efficient O(1) average time lookups. If we have seen the number, we are forced to increment it. We continue incrementing, adding 1 to our total moves count for each increment, until we find a number that has not been seen before. We then add this newly found unique number to our set of seen numbers and move on. While simple, this can be very slow if many increments are needed for a single element.
import java.util.HashSet;import java.util.Set; class Solution { public int minIncrementForUnique(int[] nums) { Set<Integer> seen = new HashSet<>(); int moves = 0; for (int num : nums) { while (seen.contains(num)) { num++; moves++; } seen.add(num); } return moves; }}Complexity
Time
O(N + M), where N is the length of `nums` and M is the total number of increments. In the worst-case scenario (e.g., an array of all zeros), M can be on the order of O(N^2), making the overall time complexity effectively O(N^2).
Space
O(N), where N is the number of elements in `nums`. In the worst case, all numbers become unique and are stored in the `HashSet`.
Trade-offs
Pros
Simple to understand and implement.
Does not require modifying the input array.
Cons
Highly inefficient for inputs with many duplicates or large values, as the inner
whileloop can execute many times.Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits for the given constraints.
This approach is based on a greedy strategy. By sorting the array first, we can process the numbers in increasing order. This allows us to make a locally optimal choice at each step that leads to a globally optimal solution. For any number that is not greater than the previous number in the sorted array, we increment it just enough to be one greater than the previous one. This is the minimum possible increment to resolve the conflict, thus minimizing the total moves.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize
moves = 0. - Iterate through the sorted array from the second element (index
i = 1) to the end. - At each element
nums[i], compare it with the previous elementnums[i-1]. - If
nums[i] <= nums[i-1], it meansnums[i]is not unique. The smallest unique value it can take isnums[i-1] + 1. - Calculate the required increment:
increment = nums[i-1] - nums[i] + 1. - Add this
incrementto the totalmoves. - Update the current element's value to its new unique value:
nums[i] = nums[i-1] + 1. This ensures the correct baseline for the next element. - If
nums[i] > nums[i-1], the element is already unique with respect to the previous ones, so no action is needed. - Return
movesafter the loop.
Walkthrough
The core idea is that after sorting, each element nums[i] must be at least nums[i-1] + 1 to be unique. If we find an element nums[i] that is less than or equal to nums[i-1], we must increment it. The minimum number of moves to make nums[i] unique is to change it to nums[i-1] + 1. We add the difference (nums[i-1] + 1) - nums[i] to our total moves and update nums[i] to this new value. This update is crucial because the next element nums[i+1] will be compared against this new, larger value of nums[i]. This greedy choice works because we've sorted the array, so we only need to ensure an element is larger than its immediate predecessor.
import java.util.Arrays; class Solution { public int minIncrementForUnique(int[] nums) { if (nums == null || nums.length == 0) { return 0; } Arrays.sort(nums); int moves = 0; for (int i = 1; i < nums.length; i++) { if (nums[i] <= nums[i-1]) { int increment = nums[i-1] - nums[i] + 1; moves += increment; nums[i] = nums[i-1] + 1; } } return moves; }}Complexity
Time
O(N log N), dominated by the initial sorting step. The subsequent linear scan of the array takes O(N) time.
Space
O(log N) or O(N), depending on the space complexity of the sorting algorithm used. Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
Trade-offs
Pros
Guaranteed to find the minimum number of moves.
Significantly more efficient than the brute-force approach.
Relatively easy to reason about after sorting.
Cons
The O(N log N) time complexity from sorting is not the fastest possible solution.
This approach modifies the input array. A copy should be made if the original array needs to be preserved.
This approach leverages the fact that the values in the array are within a manageable range. We can use a frequency array (a form of counting sort) to count the occurrences of each number. Then, we iterate through the numbers from 0 upwards. If we find a number with more than one occurrence, we know we have duplicates. We keep one and 'carry over' the extras to the next integer, adding the number of carried-over duplicates to our total moves. This is because each carried-over duplicate must be incremented at least once to move to the next integer slot.
Algorithm
- Determine the required size for a frequency array. This will be
max(nums) + nums.lengthto accommodate all original numbers and potential increments. - Create a frequency array
countsof this size, initialized to zeros. - Iterate through the input
numsand populate the frequency array: for eachnum, incrementcounts[num]. - Initialize
moves = 0. - Iterate through the
countsarray from indexi = 0up to its end. - If
counts[i] > 1, it means there are duplicates of the numberi. - The number of duplicates to be moved is
duplicates = counts[i] - 1. - These duplicates must be incremented to at least
i + 1. Addduplicatesto the totalmoves. - Carry over these duplicates to the next number's count:
counts[i+1] += duplicates. - After the loop, return the total
moves.
Walkthrough
This method avoids sorting by directly counting the numbers. We create an array, counts, large enough to hold the frequency of all numbers in the input, plus any new numbers we might generate. The maximum possible number could be max_val + N. After counting the initial frequencies, we iterate through the counts array. At any index i, if counts[i] is greater than 1, we have counts[i] - 1 duplicates. Each of these must be incremented. We add counts[i] - 1 to our total moves and pass these duplicates on to the next index by adding counts[i] - 1 to counts[i+1]. This efficiently processes all duplicates by moving them up to the next available slots in a single pass.
class Solution { public int minIncrementForUnique(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxVal = 0; for (int num : nums) { maxVal = Math.max(maxVal, num); } // The size needs to accommodate the max original value plus potential increments. // maxVal + nums.length is a safe upper bound. int[] counts = new int[maxVal + nums.length + 1]; for (int num : nums) { counts[num]++; } int moves = 0; for (int i = 0; i < counts.length - 1; i++) { if (counts[i] <= 1) { continue; } int duplicates = counts[i] - 1; moves += duplicates; counts[i+1] += duplicates; } return moves; }}Complexity
Time
O(N + K), where N is `nums.length` and K is the maximum value in `nums`. We make one pass to populate the counts (O(N)) and one pass over the counts array (O(N+K)). This is linear time.
Space
O(N + K), where N is `nums.length` and K is the maximum value in `nums`. This is for the frequency array.
Trade-offs
Pros
Achieves linear time complexity, making it the most efficient solution for the given constraints.
Avoids the O(N log N) overhead of sorting.
Cons
Requires a large amount of auxiliary space, proportional to the maximum value in the array plus its length. This can be a problem if the number range is very large.
Solutions
Solution
class Solution {public int minIncrementForUnique(int[] nums) { Arrays.sort(nums); int ans = 0; for (int i = 1; i < nums.length; ++i) { if (nums[i] <= nums[i - 1]) { int d = nums[i - 1] - nums[i] + 1; nums[i] += d; ans += d; } } return ans; }}class Solution: def minIncrementForUnique(self, nums: List[int]) -> int: nums . sort() ans = 0 for i in range(1, len(nums)): if nums[i] <= nums[i - 1]: d = nums[i - 1] - nums[i] + 1 nums[i] += d ans += d return ansclass Solution {public: int minIncrementForUnique(vector<int> &nums) { sort(nums.begin(), nums.end()); int ans = 0; for (int i = 1; i < nums.size(); ++i) { if (nums[i] <= nums[i - 1]) { int d = nums[i - 1] - nums[i] + 1; nums[i] += d; ans += d; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.