Skip to content

945. Minimum Increment to Make Array Unique

DifficultyMedium

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

Thinking

Each move increments one element; we want all values distinct at minimum cost. After sorting, each \(x\) should occupy the next free slot \(y\). Set \(y\leftarrow\max(y+1,x)\) and add \(y-x\).

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

Thinking

Sorting costs \(O(n\log n)\). With an upper bound \(m=\max+n\), a count array works: from low to high, the surplus \(cnt[i]-1\) copies of \(i\) move to \(i+1\), a linear sweep of the range.

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