0945. Minimum Increment to Make Array Unique

Problem:

Given an array of integers `nums`, we need to make the array unique. In each operation, we can increment any element by `1`. We need to find the minimum number of increments required to make all elements in the array unique.

Solution Description:

To implement the solution, we need to:

1. Sort the array `nums`.
2. Iterate through the sorted array and for each element, if it is not greater than the previous element, increment it to make it unique and count the increments.
3. Keep track of the minimum increments required to ensure all elements are unique.

The optimal solution will involve sorting the array which takes `O(n log n)` time and then a single pass through the array, resulting in an overall time complexity of `O(n log n)`. The space complexity is `O(1)` if we ignore the space required for sorting.

Example:

Let's take an example to understand the algorithm:

Given `nums = [3, 2, 1, 2, 1, 7]`.

1. Sort `nums` -> `[1, 1, 2, 2, 3, 7]`
2. Iterate through the sorted array:
   • At index 1: `nums[1]` is not greater than `nums[0]`, so increment `nums[1]` to `2`. Increment count is `1`.
   • At index 2: `nums[2]` is not greater than `nums[1]`, so increment `nums[2]` to `3`. Increment count is `2`.
   • At index 3: `nums[3]` is not greater than `nums[2]`, so increment `nums[3]` to `4`. Increment count is `4`.
   • At index 4: `nums[4]` is already greater than `nums[3]`, no increment needed.
   • At index 5: `nums[5]` is already unique.

Final array: `[1, 2, 3, 4, 3, 7]` with a total increment count of `6`.

Setup:

Here is the skeleton of the solution along with the test cases to verify the implementation.

/**
 * Finds the minimum increments required to make all elements in the array unique.
 *
 * @param {number[]} nums - The array of integers.
 * @return {number} The minimum number of increments.
 */
var minIncrementForUnique = function(nums) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

    if (nums.length === 0) return 0;

    // Sort the array
    nums.sort((a, b) => a - b);

    let c = 0;
    table(nums);
    for (let i = 1; i < nums.length; i++) {

        const cur = nums[i];
        const prev = nums[i - 1];
        log(`cur=${cur}; prev=${prev}`);

        if (prev >= cur) {
            let inc = prev - cur + 1;
            nums[i] += inc;
            c += inc;
            log(`prev=${prev}; cur=${cur}; inc=${inc}; nums[i]=${nums[i]}`);

        }
    }

    table(nums);
    return c;
};

// Test cases
const testCases = [
    { nums: [3, 2, 1, 2, 1, 7], expected: 6 },
    { nums: [1, 2, 2], expected: 1 },
    { nums: [1, 1, 1], expected: 3 },
    { nums: [], expected: 0 },
    { nums: [0, 2, 2, 2, 3], expected: 3 },
];

// [0, 2, 2, 2, 3]
// [0, 2, 3, 4, 3]

testCases.forEach((test, index) => {
    const result = minIncrementForUnique(test.nums);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});