Minimum Increment to Make Array Unique solution and explanation
Google
9 more videos on this problem
Minimum Increment to Make Array Unique - Leetcode 945 - PythonNeetCodeIO · 16:20 · 17K views
Minimum Increment to Make Array Unique | Sorting | Counting Sort | Leetcode 945 | codestorywithMIKcodestorywithMIK · 29:01 · 7K views
Minimum Increment to Make Array Unique | Leetcode #945Don Sirivat · 10:29 · 4K views
945. Minimum Increment to Make Array Unique | Greedy | Counting SortAryan Mittal · 19:49 · 4K views
LeetCode 945. Minimum Increment to Make Array UniqueHappy Coding · 21:47 · 3K views
Leetcode 945 Minimum Increment to Make Array UniqueTao Algorithm · 4:20 · 3K views
Minimum Increments to make array unique (LeetCode 945) | SortingNikhil Lohia · 12:01 · 2K views
945. Minimum Increment to Make Array Unique | Leetcode POTD 14 June 2024 | Counting Sort | GreedyAlgorithmHQ · 14:49 · 711 views
Leetcode 945 Minimum Increment to Make Array Unique涛算法 · 3:07 · 698 views
945. Minimum Increment to make array unique | With Thought process | LeetCode 945Amit Dhyani · 15:43 · 76 views
The problem
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
Approach overview
Problem Overview: You receive an integer array where duplicate values are allowed. Each move increments any element by 1. The goal is to make all elements unique while minimizing the total number of increments.
Approach 1: Sorting and Linear Scan (O(n log n) time, O(1) extra space)
This approach relies on sorting the array first so duplicates appear next to each other. After sorting, iterate through the array and ensure each element is at least one greater than the previous element. If nums[i] <= nums[i-1], increment it to nums[i-1] + 1 and add the difference to the total moves. The key insight is that after sorting, the smallest valid value for the current element depends only on the previous element. This greedy adjustment ensures the minimal increment required for uniqueness. The method uses concepts from sorting and greedy algorithms.
Approach 2: Count Array / Frequency Propagation (O(n + maxValue) time, O(maxValue) space)
This approach avoids sorting by using a frequency array to track how many times each value appears. Iterate through the count array and whenever a value appears more than once, keep one instance and push the extra occurrences to the next index. This propagation continues until all duplicates are distributed to higher values. Each propagated step represents an increment operation. The idea resembles carrying over excess frequency, similar to how counting sort manages frequencies. It works well when the range of values is manageable and leverages counting techniques on top of basic array operations.
Recommended for interviews: The sorting + linear scan solution is what most interviewers expect. It is simple, uses a clear greedy rule, and runs in O(n log n) time with constant extra space. Explaining the frequency propagation method shows deeper algorithmic thinking and can achieve near O(n) performance when the value range is small. Demonstrating both approaches shows strong problem-solving depth.
Approach 1: Sorting and Linear Scan
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.
def min_increment_for_unique(nums):
nums.sort()
moves, need = 0, nums[0]
for num in nums:
moves += max(0, need - num)
need = max(need, num) + 1
return moves
nums = [3,2,1,2,1,7]
print(min_increment_for_unique(nums))import java.util.Arrays;
public class Solution {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
int moves = 0, need = nums[0];
for (int num : nums) {
moves += Math.max(0, need - num);
need = Math.max(need, num) + 1;
}
return moves;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 1, 2, 1, 7};
System.out.println(sol.minIncrementForUnique(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minIncrementForUnique(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int moves = 0, need = nums[0];
for (const int& num : nums) {
moves += std::max(0, need - num);
need = std::max(need, num) + 1;
}
return moves;
}
int main() {
std::vector<int> nums = {3, 2, 1, 2, 1, 7};
std::cout << minIncrementForUnique(nums) << std::endl;
return 0;
}function minIncrementForUnique(nums) {
nums.sort((a, b) => a - b);
let moves = 0, need = nums[0];
for (const num of nums) {
moves += Math.max(0, need - num);
need = Math.max(need, num) + 1;
}
return moves;
}
const nums = [3,2,1,2,1,7];
console.log(minIncrementForUnique(nums));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minIncrementForUnique(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int moves = 0, need = nums[0];
for (int i = 0; i < numsSize; i++) {
moves += abs(need - nums[i]);
need = nums[i] + 1;
}
return moves;
}
int main() {
int nums[] = {3,2,1,2,1,7};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minIncrementForUnique(nums, size));
return 0;
}using System;
class Solution {
public int MinIncrementForUnique(int[] nums) {
Array.Sort(nums);
int moves = 0, need = nums[0];
foreach (int num in nums) {
moves += Math.Max(0, need - num);
need = Math.Max(need, num) + 1;
}
return moves;
}
static void Main() {
var nums = new int[]{3, 2, 1, 2, 1, 7};
var sol = new Solution();
Console.WriteLine(sol.MinIncrementForUnique(nums));
}
}This Python solution sorts the input list and processes each element to determine the number of moves required to achieve a unique array. It leverages the sorted order to ensure minimal increments.
Time Complexity: O(N log N) due to sorting, followed by O(N) for processing, therefore overall O(N log N).
Space Complexity: O(1) for in-place sorting.
Approach 2: Use Count Array
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.
def min_increment_for_unique(nums):
count = [0] * 100000
for num in nums:
count[num] += 1
moves = 0
taken = 0
for i in range(100000):
if count[i] > 1:
taken += count[i] - 1
moves -= i * (count[i] - 1)
elif taken > 0 and count[i] == 0:
taken -= 1
moves += i
return moves
nums = [3,2,1,2,1,7]
print(min_increment_for_unique(nums))import java.util.*;
public class Solution {
public int minIncrementForUnique(int[] nums) {
int[] count = new int[100000];
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;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 1, 2, 1, 7};
System.out.println(sol.minIncrementForUnique(nums));
}
}#include <iostream>
#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;
}function minIncrementForUnique(nums) {
let count = Array(100000).fill(0);
nums.forEach(num => count[num]++);
let moves = 0;
let taken = 0;
for (let i = 0; i < count.length; 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;
}
const nums = [3, 2, 1, 2, 1, 7];
console.log(minIncrementForUnique(nums));#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int minIncrementForUnique(int* nums, int numsSize) {
int count[MAX] = {0};
for(int i=0; i<numsSize; i++) count[nums[i]]++;
int moves = 0, taken = 0;
for(int i=0; i<MAX; 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() {
int nums[] = {3,2,1,2,1,7};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minIncrementForUnique(nums, size));
return 0;
}using System;
class Solution {
public int MinIncrementForUnique(int[] nums) {
int[] count = new int[100000];
foreach (var num in 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;
}
static void Main() {
var nums = new int[]{3, 2, 1, 2, 1, 7};
var sol = new Solution();
Console.WriteLine(sol.MinIncrementForUnique(nums));
}
}Python's approach utilizes a large count array to record occurrences of each number. It processes this count array to ensure uniqueness by utilizing empty slots available, calculating the moves required effectively.
Time Complexity: O(N + M), balancing occurrences and gaps.
Space Complexity: O(M), with M being the max possible value.
Approach 3: Sorting + Greedy
First, we sort the array nums, and use a variable y to record the current maximum value, initially y = -1.
Then, we iterate through the array nums. For each element x, we update y to max(y + 1, x), and accumulate the operation count y - x into the result.
After completing the iteration, we return the result.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array nums.
function minIncrementForUnique(nums: number[]): number {
nums.sort((a, b) => a - b);
let [ans, y] = [0, -1];
for (const x of nums) {
y = Math.max(y + 1, x);
ans += y - x;
}
return ans;
}func minIncrementForUnique(nums []int) (ans int) {
sort.Ints(nums)
y := -1
for _, x := range nums {
y = max(y+1, x)
ans += y - x
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Linear Scan | Time Complexity: O(N log N) due to sorting, followed by O(N) for processing, therefore overall O(N log N). |
| Use Count Array | Time Complexity: O(N + M), balancing occurrences and gaps. |
| Sorting + Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Linear Scan | O(n log n) | O(1) | General case; simplest and most common interview solution |
| Count Array / Frequency Propagation | O(n + maxValue) | O(maxValue) | When the value range is small and near-linear time is preferred |
Frequently asked questions
Is Minimum Increment to Make Array Unique easy or hard?
Minimum Increment to Make Array Unique is classified as a medium difficulty problem. The logic is straightforward once you recognize the greedy pattern after sorting, but identifying the optimal strategy without brute force requires algorithmic intuition.
How to solve Minimum Increment to Make Array Unique in O(n)?
Use a count array to track how many times each value appears. When a value appears more than once, keep one copy and push the extra occurrences to the next index, effectively simulating increments. This propagation continues until duplicates are resolved, producing an overall O(n + maxValue) time complexity.
What is the best approach for Minimum Increment to Make Array Unique?
The most practical approach is sorting followed by a linear scan. After sorting the array, iterate once and ensure every element is strictly greater than the previous one. If not, increment it to previous + 1 and accumulate the difference. This greedy strategy runs in O(n log n) time and O(1) extra space.
What data structure is used in Minimum Increment to Make Array Unique?
The problem primarily uses arrays along with greedy logic. The standard solution sorts the array and performs a linear scan, while an alternative solution uses a frequency or counting array to propagate duplicate values forward.
What is the time complexity of Minimum Increment to Make Array Unique?
The common sorting-based solution runs in O(n log n) time due to sorting, followed by a linear pass. A counting-array optimization can reduce the complexity to O(n + maxValue) when the range of numbers is limited. Space complexity is O(1) for sorting or O(maxValue) for the counting method.
Minimum Increment to Make Array Unique Python or Java solution approach?
Both Python and Java implementations typically follow the same idea: sort the array and track the minimum allowed value for the current element. If the current value is less than or equal to the previous, increment it to previous + 1 and add the increment difference to the answer.
Is Minimum Increment to Make Array Unique asked at Google, Amazon, or Meta?
Minimum Increment to Make Array Unique appears frequently in coding interviews at large tech companies and is a common medium-level greedy problem. Variants of this problem are reported in interviews at companies like Amazon and Google where array manipulation and greedy reasoning are tested.