Minimum Increment to Make Array Unique

Medium
1127.

Minimum Increment to Make Array Unique

Minimum Increment to Make Array Unique is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Uber interviews.

In one move you may pick any index i and increase nums[i] by 1.

Return the minimum number of moves needed so that every value in nums is distinct.

The test cases guarantee the answer fits in a 32-bit integer.

Example 1

Input
nums = [4,4,4]
Output
3
Explanation
Raise one 4 to 5 (1 move) and another to 6 (2 moves).

Example 2

Input
nums = [0,2,2,1]
Output
1
Explanation
One of the 2s becomes 3.

Example 3

Input
nums = [5,1,5,2,1]
Output
3
Explanation
For example `[6,1,5,3,2]`.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
  • The answer fits in a 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minIncrementForUnique = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Increment to Make Array Unique — Problem & Solution

Minimum Increment to Make Array Unique solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Increment to Make Array Unique is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Uber interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Counting
  • Asked at: Amazon, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In one move you may pick any index i and increase nums[i] by 1.

Return the minimum number of moves needed so that every value in nums is distinct.

The test cases guarantee the answer fits in a 32-bit integer.

Example 1

Input: nums = [4,4,4]
Output: 3
Explanation: Raise one 4 to 5 (1 move) and another to 6 (2 moves).

Example 2

Input: nums = [0,2,2,1]
Output: 1
Explanation: One of the 2s becomes 3.

Example 3

Input: nums = [5,1,5,2,1]
Output: 3
Explanation: For example `[6,1,5,3,2]`.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
  • The answer fits in a 32-bit integer.

Hints for Minimum Increment to Make Array Unique

  1. Hint 1

    Values can only go up, so a small value never needs to move past a larger one.

  2. Hint 2

    Sort the array. Walking left to right, what is the smallest value the current element may take?

  3. Hint 3

    Track the next free value need: an element below it is raised to need (costing need - nums[i]), otherwise it stays and need becomes nums[i] + 1.

How to solve Minimum Increment to Make Array Unique

After sorting, each element should take the smallest value that is at least itself and larger than everything already placed.

Approach

  1. Sort nums ascending.
  2. Keep need, the smallest value not yet taken by the processed prefix (start at 0).
  3. For each element: if it is below need, add need - nums[i] moves and increment need; otherwise set need = nums[i] + 1.
  4. Return the total moves.

Why it works

Processing in sorted order, the placed values form an increasing sequence ending at need - 1. Giving the current element any value above need would only push later elements higher too, and a value below need is either taken or below the element itself. An exchange argument shows that assigning final values in the same order as the sorted originals is optimal, so this greedy is minimum.

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • Moving only to the next value up (nums[i-1] + 1) without carrying need breaks on runs like [1,1,1].
  • Elements already above need must reset it, not increase the move count.
  • A counting-sort sweep over values 0..max + n also works in O(n + max).

Reference solution

Python

from typing import List

def minIncrementForUnique(nums: List[int]) -> int:
    moves = 0
    need = 0
    for v in sorted(nums):
        if v < need:
            moves += need - v
            need += 1
        else:
            need = v + 1
    return moves

Java

public static int minIncrementForUnique(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int moves = 0, need = 0;
    for (int v : a) {
        if (v < need) {
            moves += need - v;
            need++;
        } else {
            need = v + 1;
        }
    }
    return moves;
}

C++

int minIncrementForUnique(vector<int>& nums) {
    vector<int> a(nums);
    sort(a.begin(), a.end());
    int moves = 0, need = 0;
    for (int v : a) {
        if (v < need) {
            moves += need - v;
            need++;
        } else {
            need = v + 1;
        }
    }
    return moves;
}

JavaScript

var minIncrementForUnique = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var moves = 0, need = 0;
    for (var i = 0; i < a.length; i++) {
        if (a[i] < need) {
            moves += need - a[i];
            need++;
        } else {
            need = a[i] + 1;
        }
    }
    return moves;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms