Leetcode 945. Minimum Increment to Make Array Unique

Problem Explanation

You are given an array of integers and you can increment any element in the array by 1 in a single move (so adding +1 to any element is counted as a single move). The goal is to make all elements of this array unique with the least amount of "moves" as possible.

Let's take a look at an example to understand better.

Example:

Input array: [3,2,1,2,1,7]. As you can see, the array has repeated numbers 2 and 1, so it's currently not unique. To reach a state where all numbers are unique, we can make the following moves:

• Increase the second 2 in the array to 4. Now we have [3,2,1,4,1,7]. It took us 2 moves.
• Increase the second 1 in the array to 5. Now we have [3,2,1,4,5,7]. It took us 4 more moves.

So we performed total of 2 + 4 = 6 moves as output.

The solution to this problem is approached by sorting the array. Then, with each number, we either don't need to make moves if it's greater than the last added one, or make enough moves to make it one greater than the last added one.

Python Solution

1
2python
3class Solution:
4    def minIncrementForUnique(self, nums):
5        nums.sort()
6        moves = 0
7        for i in range(1, len(nums)):
8            if nums[i] <= nums[i - 1]:
9                diff = nums[i - 1] - nums[i] + 1
10                nums[i] += diff
11                moves += diff
12        return moves

The Python solution first sorts the array. For each number, if it's less or equal to the previous number, it increases the number to make it greater than the previous number and adds the difference to the count of total moves.

Java Solution

1
2java
3class Solution {
4    public int minIncrementForUnique(int[] nums) {
5        Arrays.sort(nums);
6        int moves = 0;
7        for (int i = 1; i < nums.length; i++) {
8            if (nums[i] <= nums[i - 1]) {
9                int diff = nums[i - 1] - nums[i] + 1;
10                nums[i] += diff;
11                moves += diff;
12            }
13        }
14        return moves;
15    }
16}

The Java solution is pretty similar to the Python solution. It sorts the array and then for each number, if it's less or equal to the previous number, it increases the number to make it greater than the previous one and adds the difference to the total count of moves.

Javascript Solution

1
2javascript
3class Solution {
4    minIncrementForUnique(nums) {
5        nums.sort((a, b) => a - b);
6        let moves = 0;
7        for (let i = 1; i < nums.length; i++) {
8            if (nums[i] <= nums[i - 1]) {
9                let diff = nums[i - 1] - nums[i] + 1;
10                nums[i] += diff;
11                moves += diff;
12            }
13        }
14        return moves;
15    }
16}

The Javascript solution is also similar, it sorts the array and then for each number, if it's less or equal to the previous number, it increases the number to make it greater than the previous one and adds the difference to the total count of moves.

C++ Solution

1
2C++
3class Solution {
4public:
5    int minIncrementForUnique(vector<int>& nums) {
6        sort(nums.begin(), nums.end());
7        int moves = 0;
8        for (int i = 1; i < nums.size(); i++) {
9            if (nums[i] <= nums[i - 1]) {
10                int diff = nums[i - 1] - nums[i] + 1;
11                nums[i] += diff;
12                moves += diff;
13            }
14        }
15        return moves;
16    }
17};

The C++ solution is also same, it sorts the array and then for each number, if it's less or equal to the previous number, it increases the number to make it greater than the previous one and adds the difference to the total count of moves.

C# Solution

1
2C#
3public class Solution {
4    public int MinIncrementForUnique(int[] nums) {
5        Array.Sort(nums);
6        int moves = 0;
7        for (int i = 1; i < nums.Length; i++) {
8            if (nums[i] <= nums[i - 1]) {
9                int diff = nums[i - 1] - nums[i] + 1;
10                nums[i] += diff;
11                moves += diff;
12            }
13        }
14        return moves;
15    }
16}

The C# solution is also the same, it sorts the array and then for each number, if it's less or equal to the previous number, it increases the number to make it greater than the previous one and adds the difference to the total count of moves.In a nutshell, this task involves sorting the array and then using a loop to check each element of the array. If any element is less than or equal to the previous one, the number is increased by the required amount (found by subtracting the current number from the previous one and then adding 1) and added to the total move count. This logic can be successfully implemented in various programming languages, including Python, Java, JavaScript, C++, and C#.

What makes this solution efficient is its linear time complexity. Sorting the array is done in O(n log n) time, and the remaining operations - traversing the array and making the necessary adjustments - are performed in O(n) time. Consequently, the total time complexity for the operation is O(n log n), making it suitable for large datasets.

One thing to note is that this solution modifies the original array, as it directly increases the values of the elements. If it's necessary to keep the original array unchanged, a copy should be made before the sort and increment operations.

Finally, it's important to mention that this approach could be applied in any programming language that supports array or list data structures, sorting, and for-loops. This demonstrates the universality of basic programming concepts and techniques, which is a key aspect of solving algorithmic problems.

In conclusion, making an array unique by incrementing elements can be achieved with efficient time complexity by sorting the array and then incrementing each number to make it greater than the previous one if necessary. This solution can be implemented in several popular programming languages including Python, Java, JavaScript, C++, and C#.