Skip to content

945. Minimum Increment to Make Array Unique

Description

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 <= 105
  • 0 <= nums[i] <= 105

Solutions

Solution 1: Sorting + Greedy

First, we sort the array \(\textit{nums}\), and use a variable \(\textit{y}\) to record the current maximum value, initially \(\textit{y} = -1\).

Then, we iterate through the array \(\textit{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 \(\textit{nums}\).

1
2
3
4
5
6
7
8
class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans, y = 0, -1
        for x in nums:
            y = max(y + 1, x)
            ans += y - x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, y = -1;
        for (int x : nums) {
            y = Math.max(y + 1, x);
            ans += y - x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0, y = -1;
        for (int x : nums) {
            y = max(y + 1, x);
            ans += y - x;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
func minIncrementForUnique(nums []int) (ans int) {
    sort.Ints(nums)
    y := -1
    for _, x := range nums {
        y = max(y+1, x)
        ans += y - x
    }
    return
}

1
2
3
4
5
6
7
8
9
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;
}

Solution 2: Counting + Greedy

According to the problem description, the maximum value of the result array \(m = \max(\textit{nums}) + \textit{len}(\textit{nums})\). We can use a counting array \(\textit{cnt}\) to record the occurrence count of each element.

Then, we iterate from \(0\) to \(m - 1\). For each element \(i\), if its occurrence count \(\textit{cnt}[i]\) is greater than \(1\), then we add \(\textit{cnt}[i] - 1\) elements to \(i + 1\), and accumulate the operation count into the result.

After completing the iteration, we return the result.

The time complexity is \(O(m)\), and the space complexity is \(O(m)\). Here, \(m\) is the length of the array \(\textit{nums}\) plus the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        m = max(nums) + len(nums)
        cnt = Counter(nums)
        ans = 0
        for i in range(m - 1):
            if (diff := cnt[i] - 1) > 0:
                cnt[i + 1] += diff
                ans += diff
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minIncrementForUnique(int[] nums) {
        int m = Arrays.stream(nums).max().getAsInt() + nums.length;
        int[] cnt = new int[m];
        for (int x : nums) {
            ++cnt[x];
        }
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            int diff = cnt[i] - 1;
            if (diff > 0) {
                cnt[i + 1] += diff;
                ans += diff;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        int m = *max_element(nums.begin(), nums.end()) + nums.size();
        int cnt[m];
        memset(cnt, 0, sizeof(cnt));
        for (int x : nums) {
            ++cnt[x];
        }
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            int diff = cnt[i] - 1;
            if (diff > 0) {
                cnt[i + 1] += diff;
                ans += diff;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func minIncrementForUnique(nums []int) (ans int) {
    m := slices.Max(nums) + len(nums)
    cnt := make([]int, m)
    for _, x := range nums {
        cnt[x]++
    }
    for i := 0; i < m-1; i++ {
        if diff := cnt[i] - 1; diff > 0 {
            cnt[i+1] += diff
            ans += diff
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function minIncrementForUnique(nums: number[]): number {
    const m = Math.max(...nums) + nums.length;
    const cnt: number[] = Array(m).fill(0);
    for (const x of nums) {
        cnt[x]++;
    }
    let ans = 0;
    for (let i = 0; i < m - 1; ++i) {
        const diff = cnt[i] - 1;
        if (diff > 0) {
            cnt[i + 1] += diff;
            ans += diff;
        }
    }
    return ans;
}

Comments