Solution 1 takes O(N^2) time, O(1) space, it requires sort the array. Then iterate the element 1 by 1. The point is to memorize the previous element where it reaches. Then calculate for current is based on previous reach.
// reach is the height it should reach on each element
public static int minIncrementForUnique3(int[] A) {
int ans = 0, reach = Integer.MIN_VALUE;
Arrays.sort(A);
for (int a : A) {
reach = Math.max(a, reach + 1);
ans += a >= reach ? 0 : reach - a;
}
return ans;
}
Second solution takes O(N + KlogK) time, where K is the number of different number in array. Use TreeMap to store the number for each element. Still remember previous element where it reaches.
Increment is the size for green part. Come up with a formula to calculate that part.
public static int minIncrementForUnique(int[] A) {
TreeMap<Integer, Integer> tm = new TreeMap<>();
for (int a : A) {
tm.put(a, tm.getOrDefault(a, 0) + 1);
}
int reach = Integer.MIN_VALUE, ans = 0;
for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
int key = entry.getKey(), num = entry.getValue();
reach = Math.max(reach + 1, key);
ans += reach * num + num * (num - 1) - key * num;
reach += num - 1;
}
return ans;
}
Solution 3 is similar to solution 1. Since the element in A[] won’t be greater than 4000. So create an array with length 4000. Do similar solution as solution 1.