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.
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; }}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.