Minimum Increment to Make Array Unique — Problem & Solution
Minimum Increment to Make Array Unique solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Increment to Make Array Unique is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Counting
- Asked at: Amazon, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In one move you may pick any index i and increase nums[i] by 1.
Return the minimum number of moves needed so that every value in nums is distinct.
The test cases guarantee the answer fits in a 32-bit integer.
Example 1
Input: nums = [4,4,4]
Output: 3
Explanation: Raise one 4 to 5 (1 move) and another to 6 (2 moves).
Example 2
Input: nums = [0,2,2,1]
Output: 1
Explanation: One of the 2s becomes 3.
Example 3
Input: nums = [5,1,5,2,1]
Output: 3
Explanation: For example `[6,1,5,3,2]`.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^5The answer fits in a 32-bit integer.
Hints for Minimum Increment to Make Array Unique
Hint 1
Values can only go up, so a small value never needs to move past a larger one.
Hint 2
Sort the array. Walking left to right, what is the smallest value the current element may take?
Hint 3
Track the next free value
need: an element below it is raised toneed(costingneed - nums[i]), otherwise it stays andneedbecomesnums[i] + 1.
How to solve Minimum Increment to Make Array Unique
After sorting, each element should take the smallest value that is at least itself and larger than everything already placed.
Approach
- Sort
numsascending. - Keep
need, the smallest value not yet taken by the processed prefix (start at 0). - For each element: if it is below
need, addneed - nums[i]moves and incrementneed; otherwise setneed = nums[i] + 1. - Return the total moves.
Why it works
Processing in sorted order, the placed values form an increasing sequence ending at need - 1. Giving the current element any value above need would only push later elements higher too, and a value below need is either taken or below the element itself. An exchange argument shows that assigning final values in the same order as the sorted originals is optimal, so this greedy is minimum.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Moving only to the next value up (
nums[i-1] + 1) without carryingneedbreaks on runs like[1,1,1]. - Elements already above
needmust reset it, not increase the move count. - A counting-sort sweep over values
0..max + nalso works in O(n + max).
Reference solution
Python
from typing import List
def minIncrementForUnique(nums: List[int]) -> int:
moves = 0
need = 0
for v in sorted(nums):
if v < need:
moves += need - v
need += 1
else:
need = v + 1
return movesJava
public static int minIncrementForUnique(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int moves = 0, need = 0;
for (int v : a) {
if (v < need) {
moves += need - v;
need++;
} else {
need = v + 1;
}
}
return moves;
}C++
int minIncrementForUnique(vector<int>& nums) {
vector<int> a(nums);
sort(a.begin(), a.end());
int moves = 0, need = 0;
for (int v : a) {
if (v < need) {
moves += need - v;
need++;
} else {
need = v + 1;
}
}
return moves;
}JavaScript
var minIncrementForUnique = function(nums) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var moves = 0, need = 0;
for (var i = 0; i < a.length; i++) {
if (a[i] < need) {
moves += need - a[i];
need++;
} else {
need = a[i] + 1;
}
}
return moves;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms