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] <= 105The goal of #945 Minimum Increment to Make Array Unique is to transform an integer array so that every element becomes unique using the minimum number of increments. Since you can only increase values, the challenge is to resolve duplicates efficiently while keeping the total increments as small as possible.
A common strategy is to sort the array first. After sorting, iterate through the elements and ensure that each number is at least one greater than the previous number. If the current value is less than or equal to the previous value, increment it to the smallest valid value and add the difference to the total cost. This forms a greedy approach where each step locally ensures uniqueness with minimal increments.
Another idea uses a counting / frequency approach to track duplicates and push extra occurrences forward to the next available numbers. Both strategies rely on maintaining the smallest valid unique value while processing the array. The sorting-based solution typically runs in O(n log n) time with O(1) or O(n) extra space depending on implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Greedy Adjustment | O(n log n) | O(1) or O(n) |
| Counting / Frequency Propagation | O(n + k) | O(n + k) |
NeetCodeIO
This 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.
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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int minIncrementForUnique(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int moves = 0, need = nums[0];
8 for (const int& num : nums) {
9 moves += std::max(0, need - num);
10 need = std::max(need, num) + 1;
11 }
12 return moves;
13}
14
int main() {
std::vector<int> nums = {3, 2, 1, 2, 1, 7};
std::cout << minIncrementForUnique(nums) << std::endl;
return 0;
}We utilize std::sort to sort the array and then traverse it, adjusting each number to be the next available unique value. This results in a minimal number of moves needed to ensure all elements are unique.
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.
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.
1#include <vector>
#include <cmath>
using namespace std;
int minIncrementForUnique(vector<int>& nums) {
int count[100000] = {0};
for (int num : nums) count[num]++;
int moves = 0, taken = 0;
for (int i = 0; i < 100000; ++i) {
if (count[i] > 1) {
taken += count[i] - 1;
moves -= i * (count[i] - 1);
} else if (taken > 0 && count[i] == 0) {
--taken;
moves += i;
}
}
return moves;
}
int main() {
vector<int> nums = {3, 2, 1, 2, 1, 7};
cout << minIncrementForUnique(nums) << endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting places duplicate or smaller elements next to each other, making it easy to enforce a strictly increasing order. This allows the algorithm to greedily adjust only the values that violate uniqueness, minimizing unnecessary increments.
Yes, problems involving greedy logic, duplicate handling, and array manipulation are common in technical interviews at large tech companies. This problem tests your ability to combine sorting with a greedy strategy and analyze time complexity.
The most common optimal approach is to sort the array and use a greedy strategy. After sorting, ensure each element is at least one greater than the previous element, incrementing when necessary. This minimizes the number of increments while keeping the algorithm efficient.
Arrays combined with sorting are typically sufficient for this problem. In some implementations, a frequency array or hash-based counting structure can help track duplicates and move extra values forward efficiently.
In this C++ solution, a counting array is used to determine how many times each number appears. We then manage excess numbers by replacing them into the next open positions, using a variable to track these replacements effectively.