LeetCode 945.

Intuition

After sorting, every index number should become the nearest bigger number to current value

Approach

Use Arrays sorting algorithm and greedy algorithm after sorting

Complexity

• Time complexity: O(nlogn) + O(n) = O(nlogn)

• Space complexity: O(1)

Code

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);  //nlogn
        int i = 0;
        int cnt = 0;

        for (var n : nums) { //n
            i = Math.max(i, n);
            cnt += i - n;
            i++;
        }
        return cnt;
    }
}

Check out the description of this problem at LC 945.