Leetcode 945: Minimum Increment to Make Array Unique

Input: The input consists of a single integer array `nums` containing n elements.

Example: Input: nums = [1, 2, 2]

Constraints:

• 1 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^5

Output: Return the minimum number of moves required to make all elements of `nums` unique.

Example: Output: 1

Constraints:

• The input is always valid, and the answer fits in a 32-bit integer.

Goal: The goal is to calculate the minimum moves to make all elements unique by incrementing them.

Steps:

• 1. Sort the input array `nums` to group identical elements together.

• 2. Iterate over the sorted array and check if each number can be incremented to a unique value.

• 3. Track the current maximum value and ensure each number is greater than the previous number to make the array unique.

• 4. Accumulate the number of moves needed to achieve the uniqueness.

Goal: The problem constraints ensure the array size is large, so the solution must be efficient.

Steps:

• The length of the array is between 1 and 100,000.

• Each integer in the array is between 0 and 100,000.

Assumptions:

• All elements in the array are non-negative integers.

• The array may contain duplicate elements initially.

• Input: Input: nums = [1, 2, 2]

• Explanation: In this case, the array contains two 2's. By incrementing the second 2 to 3, we make all the elements unique. This requires one move.

• Input: Input: nums = [3, 2, 1, 2, 1, 7]

• Explanation: Here, the array contains repeated 2's and 1's. To make all the values unique, we increment the second 2 to 3, the second 1 to 4, and so on. A total of 6 moves are needed to make the values unique.

Approach: The approach involves sorting the array and iterating through it to ensure each element is unique by incrementing the elements when necessary.

Observations:

• The array may contain duplicates, and the goal is to eliminate those duplicates by incrementing the values.

• Sorting the array helps to deal with duplicates efficiently by ensuring the smallest possible number is always encountered first.

Steps:

• 1. Sort the array `nums` in ascending order.

• 2. Traverse the sorted array, for each element, check if it is greater than the previous element.

• 3. If an element is equal to or less than the previous element, increment it to the next unique value and count the number of increments.

• 4. Return the total number of increments needed.

Empty Inputs:

• If the array has only one element, no moves are required.

Large Inputs:

• For large inputs, ensure the solution runs efficiently by utilizing sorting and a single pass through the array.

Special Values:

• If all elements in the array are already unique, no moves are required.

Constraints:

• Ensure the solution can handle up to 100,000 elements efficiently.

int minIncrementForUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    
    int res = 0, n = nums.size(), need = 0;
    for(int i = 0; i < n; i++) {
        res += max(need - nums[i], 0);
        need = max(nums[i], need) + 1;
    }
    return res;
}

1 : Function Declaration

int minIncrementForUnique(vector<int>& nums) {

This line defines the function `minIncrementForUnique`, which takes a vector of integers `nums` and returns the minimum number of increments needed to make the numbers unique.

2 : Sorting

    sort(nums.begin(), nums.end());

Sort the vector `nums` in ascending order to make it easier to ensure uniqueness by comparing consecutive elements.

3 : Variable Initialization

    int res = 0, n = nums.size(), need = 0;

Initialize `res` to 0 (this will store the result), `n` to the size of the vector `nums`, and `need` to 0 (this will track the minimum value that the next element must be greater than or equal to).

4 : Loop Initialization

    for(int i = 0; i < n; i++) {

Start a loop to iterate through each element in the sorted vector `nums`.

5 : Increment Calculation

        res += max(need - nums[i], 0);

For each element, calculate how much it needs to be incremented (if necessary) to make it unique. If the current element is less than `need`, add the difference to `res`.

6 : Update `need`

        need = max(nums[i], need) + 1;

Update the value of `need` to ensure the next element is strictly greater than the current element, if needed.

7 : Return Statement

    return res;

Return the total number of increments required to make all elements in `nums` unique.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The time complexity is dominated by the sorting operation, which takes O(n log n) time.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the storage of the input array, with an additional O(1) space used for counting the increments.

Leetcode 945: Minimum Increment to Make Array Unique

Explore →