Watch 10 video solutions for Minimum Increment to Make Array Unique, a medium level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 17,039 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem 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 | 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 |