medium Minimum Increment to Make Array Unique

Problem Statement

You are given an array of integers nums. In a single move, you can pick any index i, where 0 <= i < nums.length and add 1 to nums[i].

Return the minimum number of moves to make all elements in the nums unique.

Examples

Example 1

Input: nums = [4, 3, 2, 2, 1, 4]
Output: 5
Explanation: We need 1 move to increment the 4 at index 5 to 5, and then 4 moves to increment the 2 at index 4 to 6. So, we need total 5 moves.

Example 2

Input: nums = [5, 5, 5, 5, 5]
Output: 10
Explanation: Increment each subsequent 5 to get [5, 6, 7, 8, 9], needing 10 moves.

Example 3

Input: nums = [1, 1, 1, 1, 2]
Output: 9
Explanation: Increment three of the 1s to get [1, 2, 3, 4, 2] with 1 + 2 + 3 = 6 moves, then increment the second 2 to 5 to get [1, 2, 3, 4, 5] with 3 moves, needing total 9 moves.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Minimum Increment to Make Array Unique — problem

1. Why / judgment

Each move +1 on one index. Optimal strategy: never leave a hole behind a collision when a lower free slot exists — process values ascending and push excess to next integer. Two implementations: (A) sort then walk O(n log n); (B) frequency array + carry excess O(n + max). Judgment: counting sort style when max ≤ ~1e5+n; else sort.

2. Big-O derivation (K11)

n≤1e5, vals≤1e5 → freq size ~ n+max is OK (≤2e5).
Counting: O(n + maxVal + n) = O(n+U).
Sort: O(n log n).
Moves for [5,5,5,5,5] → [5,6,7,8,9] cost 0+1+2+3+4=10.

3. Pattern + when-NOT (K12)

Name: MAKE UNIQUE BY GREEDY ASCENDING / COUNTING CARRY

Recognition: min increments to distinct multiset.

When-NOT: Allowed −1 or any add → different problem. Must preserve relative order of indices → may need different cost model. If U ≫ n log n, prefer sort over huge freq array.

4. Edge hand-run (K13)

[1,1,1,1,2] → one optimal path cost 9 (statement).
Already unique [1,2,3] → 0.
Empty not allowed (n≥1).

5. Interviewer follow-ups (model answers)

Q1. Why carrying excess forward is optimal?
A: Any duplicate at i must increase to some ≥i+1; pushing step-by-step to the next free is minimal by exchange (jumping over a free hole wastes moves).

Q2. Sort vs count when?
A: U large or sparse → sort; U dense and small → count faster constants.

Q3. Can TreeSet of used values work?
A: Yes but each of n inserts log n → O(n log n) and higher constants than plain sort.

6. Short drills

Drill: [4,3,2,2,1,4] → 5.
Drill: all zeros length 4 → cost 0+1+2+3=6.

✅ Solution Minimum Increment to Make Array Unique

Problem Statement

You are given an array of integers nums. In a single move, you can pick any index i, where 0 <= i < nums.length and add 1 to nums[i].

Return the minimum number of moves to make all elements in the nums unique.

Examples

Example 1

Input: nums = [4, 3, 2, 2, 1, 4]
Output: 5
Explanation: We need 1 move to increment the 4 at index 5 to 5, and then 4 moves to increment the 2 at index 4 to 6. So, we need total 5 moves.

Example 2

Input: nums = [5, 5, 5, 5, 5]
Output: 10
Explanation: Increment each subsequent 5 to get [5, 6, 7, 8, 9], needing 10 moves.

Example 3

Input: nums = [1, 1, 1, 1, 2]
Output: 9
Explanation: Increment three of the 1s to get [1, 2, 3, 4, 2] with 1 + 2 + 3 = 6 moves, then increment the second 2 to 5 to get [1, 2, 3, 4, 5] with 3 moves, needing total 9 moves.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Solution

To solve this problem, we use a counting approach instead of sorting to maintain efficiency. First, we find the maximum value in the array to determine the range for our frequency counting array. Then, we populate this array with the frequency of each value in the input array. By iterating over the frequency count array, we ensure each value is unique by carrying over excess counts to the next value. This approach avoids the overhead of sorting and efficiently handles the uniqueness requirement.

The counting approach is effective because it directly addresses the issue of duplicate values and provides a straightforward way to ensure uniqueness with minimal operations. By keeping track of the frequency of each value and adjusting accordingly, we can achieve the desired result efficiently.

Step-by-step Algorithm

Find the maximum value in the array:
- Iterate through the array nums to determine the highest value. This will help us define the range of our frequency array.
Create a frequency count array:
- Initialize an array frequency with a size of n + max, where n is the length of nums and max is the highest value found in step 1.
Populate the frequency count array:
- Iterate through nums and for each value val, increment frequency[val] by 1.
Adjust frequencies to make all values unique:
- Iterate over the frequency array.
- For each index i in frequency:
  - If frequency[i] is less than or equal to 1, continue to the next index. It means no more moves are needed from the current index i.
  - Otherwise, calculate the excess occurrences as frequency[i] - 1.
  - Add these excess occurrences to frequency[i + 1]. (Moving all excess elements to the next index).
  - Add the excess occurrences to minMoves (to keep track of the total increments needed).
Return the total number of moves:
- The variable minMoves now contains the minimum number of increments required to make all values in nums unique.

Algorithm Walkthrough

Let's walk through the algorithm using the input [4, 3, 2, 2, 1, 4].

Find the maximum value in the array:
- Iterate through nums: [4, 3, 2, 2, 1, 4]
- Maximum value is 4.
Create a frequency count array:
- Initialize frequency array of size 6 + 4 = 10 (size of nums plus max value).
- Frequency array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
Populate the frequency count array:
- For nums[0] = 4: Increment frequency[4] by 1 → [0, 0, 0, 0, 1, 0, 0, 0, 0, 0].
- For nums[1] = 3: Increment frequency[3] by 1 → [0, 0, 0, 1, 1, 0, 0, 0, 0, 0].
- For nums[2] = 2: Increment frequency[2] by 1 → [0, 0, 1, 1, 1, 0, 0, 0, 0, 0].
- For nums[3] = 2: Increment frequency[2] by 1 → [0, 0, 2, 1, 1, 0, 0, 0, 0, 0].
- For nums[4] = 1: Increment frequency[1] by 1 → [0, 1, 2, 1, 1, 0, 0, 0, 0, 0].
- For nums[5] = 4: Increment frequency[4] by 1 → [0, 1, 2, 1, 2, 0, 0, 0, 0, 0].
Adjust frequencies to make all values unique:
- Initialize minMoves to 0.
- For i = 0: frequency[0] is 0 → continue.
- For i = 1: frequency[1] is 1 → continue.
- For i = 2: frequency[2] is 2.
  - Calculate excess as 2 - 1 = 1.
  - Increment frequency[3] by 1 → [0, 1, 2, 2, 2, 0, 0, 0, 0, 0].
  - Increment minMoves by 1 → minMoves = 1.
- For i = 3: frequency[3] is 2.
  - Calculate excess as 2 - 1 = 1.
  - Increment frequency[4] by 1 → [0, 1, 2, 2, 3, 0, 0, 0, 0, 0].
  - Increment minMoves by 1 → minMoves = 2.
- For i = 4: frequency[4] is 3.
  - Calculate excess as 3 - 1 = 2.
  - Increment frequency[5] by 2 → [0, 1, 2, 2, 3, 2, 0, 0, 0, 0].
  - Increment minMoves by 2 → minMoves = 4.
- For i = 5: frequency[5] is 2.
  - Calculate excess as 2 - 1 = 1.
  - Increment frequency[6] by 1 → [0, 1, 2, 2, 3, 2, 1, 0, 0, 0].
  - Increment minMoves by 1 → minMoves = 5.
Return the total number of moves:
- The minimum number of moves required is 5.

Code

java

class Solution {

  public int minIncrementForUnique(int[] nums) {
    int n = nums.length;
    int max = 0;
    int minMoves = 0;

    // Find the maximum value in the array
    for (int value : nums) {
      max = Math.max(max, value);
    }

    // Create a frequency array to count occurrences
    int[] frequency = new int[n + max];

    // Populate the frequency array
    for (int value : nums) {
      frequency[value]++;
    }

    // Adjust frequencies to make all values unique
    for (int i = 0; i < frequency.length; i++) {
      if (frequency[i] <= 1) continue; // Skip if frequency is 1 or less

      int excess = frequency[i] - 1; // Calculate excess duplicates
      frequency[i + 1] += excess; // Move excess to the next value
      minMoves += excess; // Count moves required
    }

    return minMoves; // Return total moves
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(
      solution.minIncrementForUnique(new int[] { 4, 3, 2, 2, 1, 4 })
    ); // Output: 5
    System.out.println(
      solution.minIncrementForUnique(new int[] { 5, 5, 5, 5, 5 })
    ); // Output: 10
    System.out.println(
      solution.minIncrementForUnique(new int[] { 1, 1, 1, 1, 2 })
    ); // Output: 9
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm can be broken down into the following steps:

Finding the maximum value in the array:
Populating the frequency array:
Iterating over the frequency array to adjust the counts: , where max is the maximum value in the array.

Overall, the time complexity is .

Space Complexity

The space complexity is determined by the size of the frequency array, which is n + max. Hence, the space complexity is .

🎯 STRICT STANDOUT — Solution Minimum Increment to Make Array Unique

1. Why / judgment

frequency[val]++. Walk i ascending: if frequency[i] > 1, excess = frequency[i]−1 moves += excess; frequency[i+1] += excess; frequency[i] = 1. This is counting-sort order without materializing the full sorted array.

2. Big-O derivation (K11)

Build freq O(n). Walk domain O(max+n).
[4,3,2,2,1,4]:
freq before: 1:1 2:2 3:1 4:2
i=2: excess1 → moves1, f[3]+=1 → f3=2
i=3: excess1 → moves2, f[4]+=1 → f4=3
i=4: excess2 → moves4, f[5]+=2
i=5: excess1 → moves5, f[6]+=1
i=6: f=1 stop. moves=5 ✓ matches sort path [1,2,3,4,5,6].
[5,5,5,5,5] → moves 10 ✓

3. Pattern + when-NOT (K12)

Name: COUNTING CARRY / LINEAR GREEDY ON DOMAIN

Recognition: duplicates resolved by pushing to next free integer.

When-NOT: Need actual final array contents with original indices → must track which indices moved, not just move count.

4. Edge hand-run (K13)

[0,0] → moves 1 → values {0,1}.
Single element → 0.
Max element many dups: ensure freq array length ≥ max+n.

5. Interviewer follow-ups (model answers)

Q1. Why size n+max for frequency?
A: Worst case all equal to max → final values occupy max..max+n−1.

Q2. Integer overflow on moves?
A: moves ≤ n(n−1)/2 worst; for n=1e5 use 64-bit.

Q3. Is this counting sort?
A: Related: we use count buckets and process keys in order — same skeleton as counting sort’s key scan.

6. Short drills

Drill: hand-run [1,2,2] → moves 1.
Drill: compare moves with sort method on same input.

🧩 Pattern · Hashing

Recognize it: Membership / frequency / “have I seen this?” in O(1) → a hash map or set.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Minimum Increment to Make Array Unique? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Minimum Increment to Make Array Unique** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Minimum Increment to Make Array Unique** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Minimum Increment to Make Array Unique**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Minimum Increment to Make Array Unique**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Range Minimum Query Minimum Number of Steps to Make Tw →