Minimum Increment to Make Array Unique - Solution & Explanation
Problem Statement
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.
First, we sort the array. We then iterate over the sorted array while tracking the next needed number to ensure uniqueness. For each element, we calculate the necessary moves by comparing it to the needed value, increment the moves counter accordingly, and then determine what the next needed unique value would be.
Complexity
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.
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.
We count the occurrences of each number in the array using a fixed-size count array. Excess occurrences (duplicates) are queued for repositioning to the next available slot found.
Complexity
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.
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting and Linear Scan | Time Complexity: O(N log N) due to sorting and O(N) for linear traversal, resulting in O(N log N) overall. |
| Use Count Array | Time Complexity: O(N + M) where M is the range of numbers, due to counting and traversal. |
| Sorting + Greedy | — |
Detailed 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 |
Video Solution
Minimum Increment to Make Array Unique - Leetcode 945 - Python • NeetCodeIO • 17,362 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Increment to Make Array Unique easy or hard?
How to solve Minimum Increment to Make Array Unique in O(n)?
What is the best approach for Minimum Increment to Make Array Unique?
What data structure is used in Minimum Increment to Make Array Unique?
What is the time complexity of Minimum Increment to Make Array Unique?
Minimum Increment to Make Array Unique Python or Java solution approach?
Is Minimum Increment to Make Array Unique asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Minimum Increment to Make Array Unique with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor