Teaching Kids Programming – Minimum Increment to Make Array Unique (Sorting/Greedy)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 with 5 or less moves that it is impossible for the array to have all unique values.

Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

Minimum Increment to Make Array Unique (Sorting/Greedy)

We sort the array in order to handle the duplicates better since the same numbers are placed next to each other after sorting. Then we iterate from left to right, and accumulate the number required to make the current number different to the previous. Then we need to update the current number. This propagates to the end.

We want to preserve the order, for example, two numbers a and a+h, there is no point to increment a to anything above a+h as this will not be optimal.

Sorting requires O(NLogN) where N is the number of the elements in the array, and another O(N) loop to iterate over the array. The overall time complexity is O(NLogN) as the sorting dominates.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        n = len(nums)
        for i in range(1, n):
            if nums[i] <= nums[i - 1]:
                ans += nums[i - 1] - nums[i] + 1
                nums[i] = nums[i - 1] + 1
        return ans

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        n = len(nums)
        for i in range(1, n):
            if nums[i] <= nums[i - 1]:
                ans += nums[i - 1] - nums[i] + 1
                nums[i] = nums[i - 1] + 1
        return ans

This approach combines sorting and Greedy Algorithm, as we are greedily (after sorting) increment the numbers from smallest to the largest.

–EOF (The Ultimate Computing & Technology Blog) —